P16915 [JLCPC 2026] Roco Kingdom World.

tarjen has been playing Roco Kingdom recently, and he wants to catch some shiny sprites. During the process of farming shiny sprites, tarjen first needs to keep catching **normal sprites**. Catching normal sprites can accumulate the contamination progress of a shiny pool. When the contamination progress reaches the requirement, a **contaminated sprite** of the corresponding pool will spawn on the map. After defeating a contaminated sprite, there is a chance to encounter a **shiny sprite**. However, the number of contaminated sprites on the map is limited. If too many contaminated sprites spawn, old contaminated sprites will be pushed out by new ones. Meanwhile, the game has a guaranteed (pity) mechanism for spawning shiny sprites. Each shiny pool has an independent pity counter. Each time you defeat a contaminated sprite of the current pool, the pity counter of that pool increases by one. When the pity counter of a pool reaches $80$, then after defeating a contaminated sprite this time, you will definitely encounter a shiny sprite. **The detailed rules are as follows.** There are $n$ types of normal sprites, $A$ families, and $B$ elements. The $i$-th type of normal sprite belongs to family $\mathit{fa}_i$ and has element $\mathit{el}_i$. There are two kinds of shiny pools in the game: - **Family pool** $F_x$: the shiny pool of the $x$-th family. - **Element pool** $E_x$: the shiny pool of the $x$-th element. Each shiny pool $P$ maintains four values: - $\mathsf{progress}_P$: contamination progress, initially $0$. - $\mathsf{pity}_P$: pity counter, initially $0$. - $\mathsf{need}_P$: the number of normal catches required to spawn one contaminated sprite (a given constant). - $\mathsf{luck}_P$: the luck threshold (a given constant). At most $m$ contaminated sprites can exist on the map at the same time. All contaminated sprites are arranged into a queue from earliest spawn time to latest. If the number exceeds $m$, keep removing the front contaminated sprites until the number is at most $m$. A contaminated sprite pushed out due to the map capacity is not considered defeated, and it will not affect the pity counter of any pool. There are $q$ operations, each is one of the following two types: - **Normal catch** `C T x c` This means tarjen catches the $x$-th type of normal sprite consecutively $c$ times, and counts these $c$ catches into one kind of shiny pool. If $T = F$, they are counted into the family pool $F_{\mathit{fa}_x}$; if $T = E$, they are counted into the element pool $E_{el_x}$. Let the pool counted in this catch be $P$. Set $\mathsf{progress}_P \mathrel{+}= c$. Then, whenever $\mathsf{progress}_P \ge \mathsf{need}_P$, spawn one contaminated sprite belonging to pool $P$, and set $\mathsf{progress}_P \mathrel{-}= \mathsf{need}_P$. Note that one normal catch operation may spawn multiple contaminated sprites. Append the contaminated sprites spawned in this operation to the back of the queue in order; if the number exceeds $m$, remove contaminated sprites from the front. - **Defeat a contaminated sprite** `B k r` This means tarjen chooses to challenge the $k$-th contaminated sprite on the current map from oldest to newest. If the number of contaminated sprites on the current map is less than $k$, output `MISS`, and this operation does not change any state. Otherwise, suppose this contaminated sprite belongs to pool $P$. Remove it from the map, and set $\mathsf{pity}_P \mathrel{+}= 1$. Then perform the **shiny check**. Each pool $P$ has a luck threshold $\mathsf{luck}_P$. If $r \le \mathsf{luck}_P$ or $\mathsf{pity}_P = 80$, then a shiny is encountered this time, and set $\mathsf{pity}_P = 0$; otherwise, the pity counter is not reset. See the output section for the exact output format.

The first line contains five integers $n, A, B, m, q$（$\boldsymbol{1 \le n, A, B, m, q \le 2 \times 10^5}$), representing the number of normal sprite types, the number of families, the number of elements, the maximum number of contaminated sprites that can exist on the map at the same time, and the number of operations. The next $n$ lines each contain two integers $\mathit{fa}_i, \mathit{el}_i$ ($1 \le \mathit{fa}_i \le A$, $1 \le \mathit{el}_i \le B$). The next line contains $A$ integers $\mathsf{need}_{F_1}, \ldots, \mathsf{need}_{F_A}$ ($1 \le \mathsf{need}_{F_i} \le 10^9$). The next line contains $B$ integers $\mathsf{need}_{E_1}, \ldots, \mathsf{need}_{E_B}$ ($1 \le \mathsf{need}_{E_i} \le 10^9$). The next line contains $A$ integers $\mathsf{luck}_{F_1}, \ldots, \mathsf{luck}_{F_A}$ ($0 \le \mathsf{luck}_{F_i} \le 10^9$). The next line contains $B$ integers $\mathsf{luck}_{E_1}, \ldots, \mathsf{luck}_{E_B}$ ($0 \le \mathsf{luck}_{E_i} \le 10^9$). The next $q$ lines each describe an operation. The format is `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}$).

For each `B` operation, output one line: - If there are fewer than $k$ contaminated sprites on the map, output `MISS`. - Otherwise, if a shiny is encountered, output `SHINY F x` or `SHINY E x`. - Otherwise, if no shiny is encountered, output `NORMAL F x p` or `NORMAL E x p`, where $x$ is the index of the corresponding shiny pool, and $p$ is the current pity counter of that pool.

For sample 2, we use $\mathit{F1}$ to denote a contaminated sprite of pool $F\ 1$, and $\mathit{E1}$ to denote a contaminated sprite of pool $E\ 1$. - After the first two catch operations, the contaminated sprites on the map are $[\mathit{F1}, \mathit{E1}, \mathit{E1}]$. - Execute `B 2 50`: defeat the 2nd one ($\mathit{E1}$). Since $50 > \mathsf{luck}_{E1} = 10$ and $\mathsf{pity}_{E1} = 1 \ne 80$, output `NORMAL E 1 1`. - Then catch the 3rd type of sprite and count it into the family pool, spawning $2$ $\mathit{F2}$. The map capacity is $3$, so after the old ones are pushed out it becomes $[\mathit{E1}, \mathit{F2}, \mathit{F2}]$. - Execute `B 3 3`: defeat the 3rd one ($\mathit{F2}$). Since $3 \le \mathsf{luck}_{F2} = 5$, a shiny is encountered, output `SHINY F 2`. - Execute `B 5 1`: there are fewer than $5$ on the current map, output `MISS`. - The last defeated one is $\mathit{F1}$, no shiny is encountered, output `NORMAL F 1 1`. Translated by ChatGPT 5