E. Roco Kingdom World
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$tarjen$$$ has recently been playing Roco Kingdom and wants to catch some shiny spirits.

To farm shiny spirits, $$$tarjen$$$ must first repeatedly catch regular spirits. Catching regular spirits accumulates the pollution progress of a shiny pool. When the pollution progress reaches the required threshold, a corrupted spirit belonging to that pool spawns on the map. After defeating a corrupted spirit, there is a chance to encounter a shiny spirit.

However, the number of corrupted spirits on the map is limited. If too many spawn, old corrupted spirits are pushed out by new ones.

Additionally, there is a pity mechanism for shiny encounters. Each shiny pool has an independent pity counter. Each time a corrupted spirit from that pool is defeated, the pool's pity counter increases by one. When a pool's pity counter reaches $$$80$$$, defeating a corrupted spirit from that pool is guaranteed to trigger a shiny encounter.

The detailed rules are as follows.

There are $$$n$$$ types of regular spirits, $$$A$$$ families, and $$$B$$$ elements. The $$$i$$$-th type of regular spirit belongs to family $$$fa_i$$$ and has element $$$el_i$$$.

There are two types of shiny pools:

  • Family pool $$$F_x$$$: the shiny pool for the $$$x$$$-th family.
  • Element pool $$$E_x$$$: the shiny pool for the $$$x$$$-th element.

Each shiny pool $$$P$$$ maintains four values:

  • $$$progress_P$$$: pollution progress, initially $$$0$$$.
  • $$$pity_P$$$: pity counter, initially $$$0$$$.
  • $$$need_P$$$: the number of regular catches needed to spawn one corrupted spirit (a given constant).
  • $$$luck_P$$$: the luck threshold (a given constant).

At most $$$m$$$ corrupted spirits can exist on the map simultaneously. All corrupted spirits are arranged in a queue ordered by spawn time (oldest first). If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front until the count is at most $$$m$$$. Corrupted spirits pushed out by the map capacity are not considered defeated and do not affect any pool's pity counter.

There are $$$q$$$ operations, each being one of the following two types.

Operation 1: Regular Catch

C T x c

$$$tarjen$$$ catches the $$$x$$$-th type of regular spirit $$$c$$$ times consecutively, crediting these $$$c$$$ catches to a certain shiny pool. If $$$T = F$$$, credit to family pool $$$F_{fa_x}$$$; if $$$T = E$$$, credit to element pool $$$E_{el_x}$$$.

Let the credited pool be $$$P$$$. Set $$$progress_P \mathrel{+}= c$$$. Then, whenever $$$progress_P \ge need_P$$$, spawn one corrupted spirit belonging to pool $$$P$$$ and set $$$progress_P \mathrel{-}= need_P$$$.

Note that a single catch operation may spawn multiple corrupted spirits.

The newly spawned corrupted spirits are appended to the end of the queue in order. If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front.

Operation 2: Defeat Corrupted Spirit

B k r

$$$tarjen$$$ challenges the $$$k$$$-th corrupted spirit on the map (ordered from oldest to newest).

If there are fewer than $$$k$$$ corrupted spirits on the map, output MISS and no state changes occur.

Otherwise, let the corrupted spirit belong to pool $$$P$$$. Remove it from the map and set $$$pity_P \mathrel{+}= 1$$$.

Then perform the shiny check. Each pool $$$P$$$ has a luck threshold $$$luck_P$$$. If $$$r \le luck_P$$$ or $$$pity_P = 80$$$, a shiny is encountered: output SHINY P and set $$$pity_P = 0$$$. Otherwise, output NORMAL P $$$pity_P$$$.

Input

The first line contains five integers $$$n, A, B, m, q$$$ ($$$\boldsymbol{1 \le n, A, B, m, q \le 2 \times 10^5}$$$) — the number of regular spirit types, the number of families, the number of elements, the maximum number of corrupted spirits on the map, and the number of operations.

The next $$$n$$$ lines each contain two integers $$$fa_i, el_i$$$ ($$$1 \le fa_i \le A$$$, $$$1 \le el_i \le B$$$).

The next line contains $$$A$$$ integers $$$need_{F_1}, \ldots, need_{F_A}$$$ ($$$1 \le need_{F_i} \le 10^9$$$).

The next line contains $$$B$$$ integers $$$need_{E_1}, \ldots, need_{E_B}$$$ ($$$1 \le need_{E_i} \le 10^9$$$).

The next line contains $$$A$$$ integers $$$luck_{F_1}, \ldots, luck_{F_A}$$$ ($$$0 \le luck_{F_i} \le 10^9$$$).

The next line contains $$$B$$$ integers $$$luck_{E_1}, \ldots, luck_{E_B}$$$ ($$$0 \le luck_{E_i} \le 10^9$$$).

The next $$$q$$$ lines each describe an operation in the format C T x c ($$$\boldsymbol{T \in \{F, E\}}$$$, $$$\boldsymbol{1 \le x \le n}$$$, $$$\boldsymbol{1 \le c \le 10^{18}}$$$) or B k r ($$$\boldsymbol{1 \le k \le 10^{18}}$$$, $$$\boldsymbol{1 \le r \le 10^9}$$$).

Output

For each B operation, output one line. If there are fewer than $$$k$$$ corrupted spirits on the map, output MISS. Otherwise, if a shiny is encountered, output SHINY F x or SHINY E x; if not, output NORMAL F x p or NORMAL E x p, where $$$x$$$ is the shiny pool index and $$$p$$$ is the pool's current pity counter.

Examples
Input
5 2 2 5 10
1 2
1 1
2 2
1 1
2 2
2 2
2 3
40 5
4 41
C E 5 9
C E 4 5
B 2 608984673
B 4 918347739
B 4 37535012
C E 5 7
B 1 712704464
C F 4 7
B 3 270899745
B 5 363752455
Output
NORMAL E 2 1
NORMAL E 1 1
MISS
NORMAL E 2 2
NORMAL F 1 1
MISS
Input
3 2 1 3 8
1 1
1 1
2 1
2 3
2
0 5
10
C F 1 2
C E 2 4
B 2 50
C F 3 6
B 3 3
B 5 1
C F 1 2
B 3 100
Output
NORMAL E 1 1
SHINY F 2
MISS
NORMAL F 1 1
Note

For sample 2:

Let $$$\mathit{F1}$$$ denote a corrupted spirit from pool $$$F\ 1$$$, and $$$\mathit{E1}$$$ denote a corrupted spirit from pool $$$E\ 1$$$.

After the first two catch operations, the corrupted spirits on the map are $$$[\mathit{F1}, \mathit{E1}, \mathit{E1}]$$$.

Execute B 2 50: defeat the 2nd spirit ($$$\mathit{E1}$$$). $$$50 \gt luck_{E1} = 10$$$ and $$$pity = 1 \ne 80$$$, output NORMAL E 1 1.

Then catch the 3rd type of spirit and credit to the family pool, spawning $$$2$$$ copies of $$$\mathit{F2}$$$. Map capacity is $$$3$$$, so after eviction the map becomes $$$[\mathit{E1}, \mathit{F2}, \mathit{F2}]$$$.

Execute B 3 3: defeat the 3rd spirit ($$$\mathit{F2}$$$). $$$3 \le luck_{F2} = 5$$$, shiny encountered, output SHINY F 2.

Execute B 5 1: fewer than $$$5$$$ spirits on the map, output MISS.

The last defeat is $$$\mathit{F1}$$$, no shiny encountered, output NORMAL F 1 1.