AT_abc471_g [ABC471G] Caeser Syllables

有 $K$ 种符号，编号为 $0$ 到 $K-1$。 每个符号要么是元音，要么不是元音。当 $V_j = 1$ 时，符号 $j$ 是**元音**；当 $V_j = 0$ 时，符号 $j$ 不是元音。 一个符号串的**音节数**定义为该符号串中**仅由元音组成的极大连续子段**的数量。形式化地，对于长度为 $N$ 的符号串 $(a_1, \dots, a_N)$，其音节数为满足以下所有条件的整数对 $(l, r)$（$1 \le l \le r \le N$）的数量： - 符号 $a_l, \dots, a_r$ 全部是元音； - 若 $l > 1$，则符号 $a_{l-1}$ 不是元音； - 若 $r < N$，则符号 $a_{r+1}$ 不是元音。 给定长度为 $N$ 的数列 $A = (A_1, \dots, A_N)$。对于每个 $k = 0, \dots, K-1$，回答以下问题： - 定义长度为 $N$ 的符号串 $A' = (A'_1, \dots, A'_N)$，其中 $A'_i := (A_i + k) \bmod K$。求 $A'$ 的音节数。

输入第一行包含六个整数 $N, K, \mathrm{seed}, M$。 接下来一行包含 $M$ 个整数 $b_1, b_2, \dots, b_M$。 接下来一行包含 $K$ 个整数 $V_0, V_1, \dots, V_{K-1}$。 本题使用一种特殊的输入方式。题目不直接给出 $A_1, \dots, A_N$，而是给出 $\mathrm{seed}, M, b_1, \dots, b_M$。请按照以下伪代码恢复 $A_1, \dots, A_N$： $$ \def\arraystretch{1.2} \begin{array}{ll} \hline & \mathrm{state} \leftarrow \mathrm{seed} \\ &\textbf{for }i = 1, \dots, N: \\ &\qquad\textbf{if}\ \ i \leq M :\\ &\qquad \qquad\qquad A_i \leftarrow b_i\\ &\qquad\textbf{else}: \\ & \qquad\qquad x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32} \\ &\qquad\qquad r \leftarrow \mathrm{state} \gg 59 \\ &\qquad\qquad y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32} \\ &\qquad\qquad A_i \leftarrow y \bmod K \\ &\qquad\qquad \mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}\\ \hline \end{array} $$ 其中： - $\oplus$ 表示按位异或（XOR）； - $\gg$ 表示右移位运算（$\lfloor s / 2^t \rfloor$）； - $\ll$ 表示左移位运算（$s \times 2^t$）； - 所有变量均为无符号 64 位整数。

输出 $K$ 行。第 $m$ 行（$1 \le m \le K$）输出 $k = m-1$ 时的答案。

**【样例 1 解释】** 该样例中 $A = (4, 2, 4, 1)$。 - $k = 0$ 时，$A' = (4, 2, 4, 1)$，音节数为 $2$； - $k = 1$ 时，$A' = (5, 3, 5, 2)$，音节数为 $0$； - $k = 2$ 时，$A' = (0, 4, 0, 3)$，音节数为 $1$； - $k = 3$ 时，$A' = (1, 5, 1, 4)$，音节数为 $2$； - $k = 4$ 时，$A' = (2, 0, 2, 5)$，音节数为 $1$； - $k = 5$ 时，$A' = (3, 1, 3, 0)$，音节数为 $2$。 **【样例 2 解释】** 该样例中 $A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5)$。 **【数据范围】** - $1 \le N \le 7 \times 10^6$； - $1 \le K \le 2300$； - $0 \le A_i \le K-1$（$1 \le i \le N$）； - $V_j \in \{0, 1\}$（$0 \le j \le K-1$）； - $0 \le \mathrm{seed} \le 2^{60} - 1$； - $1 \le M \le \min(N, 10^5)$； - $0 \le b_i \le K-1$（$1 \le i \le M$）； - 所有输入值均为整数。