P16915 [JLCPC 2026] 洛克王国世界

tarjen 最近在玩洛克王国，他想要捉一些异色精灵。 在刷异色精灵的过程中，tarjen 需要先不断捕捉**普通精灵**，捕捉普通精灵可以积累异色池的污染进度。当污染进度达到要求时，地图上会刷新出对应池子的**污染精灵**。在击败污染精灵后，有机会遇到**异色精灵**。 不过，地图上的污染精灵数量有限。如果污染精灵刷得太多，旧的污染精灵会被新的污染精灵挤掉。 同时，游戏中存在刷新异色精灵的保底机制。每个异色池有独立的保底计数。每击败一次当前池子的污染精灵，该池子的保底计数加一。当某个池子的保底计数达到 $80$ 时，本次击败污染精灵后一定会遇到异色精灵。 **具体规则如下。** 共有 $n$ 种普通精灵，$A$ 个家族和 $B$ 个属性。第 $i$ 种普通精灵属于家族 $\mathit{fa}_i$，属性为 $\mathit{el}_i$。 游戏中共有两类异色池： - **家族池** $F_x$：第 $x$ 个家族的异色池。 - **属性池** $E_x$：第 $x$ 个属性的异色池。 每个异色池 $P$ 维护了四个值： - $\mathsf{progress}_P$：污染进度，初始为 $0$。 - $\mathsf{pity}_P$：保底计数，初始为 $0$。 - $\mathsf{need}_P$：刷新一只污染精灵所需的普通捕获次数（给定常数）。 - $\mathsf{luck}_P$：幸运阈值（给定常数）。 地图中最多同时存在 $m$ 只污染精灵。所有污染精灵按刷新时间从早到晚排成一个队列。若数量超过 $m$，则不断移除队首的污染精灵，直到数量不超过 $m$。被地图容量挤掉的污染精灵不会被视为击败，也不会影响任何池子的保底计数。 共有 $q$ 次操作，每次操作为以下两种之一： - **普通捕获** `C T x c` 表示 tarjen 连续捕获第 $x$ 种普通精灵 $c$ 次，并将这 $c$ 次捕获计入某一类异色池。若 $T = F$，则计入家族池 $F_{\mathit{fa}_x}$；若 $T = E$，则计入属性池 $E_{el_x}$。 设本次捕获计入的池子为 $P$，则令 $\mathsf{progress}_P \mathrel{+}= c$。然后，每当 $\mathsf{progress}_P \ge \mathsf{need}_P$，就刷新出一只属于池子 $P$ 的污染精灵，并令 $\mathsf{progress}_P \mathrel{-}= \mathsf{need}_P$。 注意，一次普通捕获可能会刷新出多只污染精灵。 将本次刷新出的污染精灵依次加入队列尾部，若数量超过 $m$ 则移除队首的污染精灵。 - **击败污染精灵** `B k r` 表示 tarjen 选择当前地图中从旧到新第 $k$ 只污染精灵进行挑战。 若当前地图中的污染精灵数量不足 $k$，则输出 `MISS`，本次操作不改变任何状态。 否则，设该污染精灵属于池子 $P$。将其从地图中移除，并令 $\mathsf{pity}_P \mathrel{+}= 1$。 然后进行**异色判定**。每个池子 $P$ 有一个幸运阈值 $\mathsf{luck}_P$。若满足 $r \le \mathsf{luck}_P$ 或 $\mathsf{pity}_P = 80$，则本次遇到异色，并令 $\mathsf{pity}_P = 0$；否则不重置保底计数。具体输出格式见输出部分。

第一行包含五个整数 $n, A, B, m, q$（$\boldsymbol{1 \le n, A, B, m, q \le 2 \times 10^5}$），分别表示普通精灵种类数、家族数量、属性数量、地图中最多同时存在的污染精灵数量以及操作次数。 接下来 $n$ 行，每行两个整数 $\mathit{fa}_i, \mathit{el}_i$（$1 \le \mathit{fa}_i \le A$，$1 \le \mathit{el}_i \le B$）。 接下来一行 $A$ 个整数 $\mathsf{need}_{F_1}, \ldots, \mathsf{need}_{F_A}$（$1 \le \mathsf{need}_{F_i} \le 10^9$）。 接下来一行 $B$ 个整数 $\mathsf{need}_{E_1}, \ldots, \mathsf{need}_{E_B}$（$1 \le \mathsf{need}_{E_i} \le 10^9$）。 接下来一行 $A$ 个整数 $\mathsf{luck}_{F_1}, \ldots, \mathsf{luck}_{F_A}$（$0 \le \mathsf{luck}_{F_i} \le 10^9$）。 接下来一行 $B$ 个整数 $\mathsf{luck}_{E_1}, \ldots, \mathsf{luck}_{E_B}$（$0 \le \mathsf{luck}_{E_i} \le 10^9$）。 接下来 $q$ 行，每行描述一个操作。格式为 `C T x c`（$\boldsymbol{T \in \{F, E\}}$，$\boldsymbol{1 \le x \le n}$，$\boldsymbol{1 \le c \le 10^{18}}$）或 `B k r`（$\boldsymbol{1 \le k \le 10^{18}}$，$\boldsymbol{1 \le r \le 10^9}$）。

对于每个 `B` 操作，输出一行结果： - 若地图中不足 $k$ 只污染精灵，输出 `MISS`； - 否则，若遇到异色，输出 `SHINY F x` 或 `SHINY E x`； - 否则，若未遇到异色，输出 `NORMAL F x p` 或 `NORMAL E x p`，其中 $x$ 为对应异色池编号， $p$ 为该池子当前的保底计数。

对于样例 2，我们用 $\mathit{F1}$ 表示池子 $F\ 1$ 的污染精灵，$\mathit{E1}$ 表示池子 $E\ 1$ 的污染精灵。 - 前两次捕获后，地图中的污染精灵为 $[\mathit{F1}, \mathit{E1}, \mathit{E1}]$。 - 执行 `B 2 50`：击败第 $2$ 只（$\mathit{E1}$）。$50 > \mathsf{luck}_{E1} = 10$ 且 $\mathsf{pity}_{E1} = 1 \ne 80$，输出 `NORMAL E 1 1`。 - 之后捕获第 $3$ 种精灵并计入家族池，刷新 $2$ 只 $\mathit{F2}$。地图容量为 $3$，旧的被挤掉后变为 $[\mathit{E1}, \mathit{F2}, \mathit{F2}]$。 - 执行 `B 3 3`：击败第 $3$ 只（$\mathit{F2}$）。$3 \le \mathsf{luck}_{F2} = 5$，遇到异色，输出 `SHINY F 2`。 - 执行 `B 5 1`：当前地图不足 $5$ 只，输出 `MISS`。 - 最后一次击败的是 $\mathit{F1}$，未遇到异色，输出 `NORMAL F 1 1`。