AT_abc471_g.Caeser Syllables

There are $K$ kinds of symbols numbered $0$ to $K-1$.

Each symbol is either a vowel or not a vowel. If $V_j = 1$, symbol $j$ is a vowel; if $V_j = 0$, symbol $j$ is not a vowel.

Define the number of syllables of a symbol string as the number of maximal contiguous substrings of that string consisting of vowels. Formally, the number of syllables of a length-$N$ symbol string $(a_1, \dots, a_N)$ is defined as the number of pairs of integers $(l,r)$ satisfying $1 \leq l \leq r \leq N$ and all of the following:

• The symbols $a_l, \dots, a_r$ are all vowels.
• If $l > 1$, symbol $a_{l-1}$ is not a vowel.
• If $r < N$, symbol $a_{r+1}$ is not a vowel.

You are given a length-$N$ sequence $A = (A_1, \dots, A_N)$. For each $k = 0, \dots, K-1$, answer the following question:

• Define a length-$N$ symbol string $A' = (A'_1, \dots, A'_N)$ by $A'_i := (A_i + k) \bmod K$. What is the number of syllables of $A'$?

共有 $K$ 种符号，编号为 $0$ 到 $K-1$。

每种符号要么是元音，要么不是元音。若 $V_j = 1$，则符号 $j$ 是元音；若 $V_j = 0$，则符号 $j$ 不是元音。

定义一个符号串的音节数为该串中由元音构成的极大连续子串的个数。形式化地，长度为 $N$ 的符号串 $(a_1, \dots, a_N)$ 的音节数定义为满足 $1 \leq l \leq r \leq N$ 且同时满足以下所有条件的整数对 $(l,r)$ 的个数：

• 符号 $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'$ 的音节数。

The input is given from Standard Input in the following format:

$N$ $K$ $\mathrm{seed}$ $M$
$b_1$ $b_2$ $\cdots$ $b_M$
$V_0$ $V_1$ $\cdots$ $V_{K-1}$

输入从标准输入中按以下格式给出：

$N$ $K$ $\mathrm{seed}$ $M$
$b_1$ $b_2$ $\cdots$ $b_M$
$V_0$ $V_1$ $\cdots$ $V_{K-1}$

Output $K$ lines. The $m$-th line ($1 \leq m \leq K$) should contain the answer for $k = m-1$.

输出 $K$ 行。第 $m$ 行（$1 \leq m \leq K$）应包含 $k = m-1$ 时的答案。

Input Format

The input for this problem is given in a special format.

Instead of $A_1, \dots, A_N$, the integers $\mathrm{seed}, M, b_1, \dots, b_M$ are given from Standard Input. Restore $A_1, \dots, A_N$ using the computation represented by the following pseudocode.

Here, all variables in the pseudocode are unsigned $64$-bit integers. $s \oplus t$ denotes the bitwise XOR of $s$ and $t$, $s \gg t$ denotes $\lfloor s / 2^t \rfloor$ (the right shift operation), and $s \ll t$ denotes $s \times 2^t$ (the left shift operation).

$\mathrm{state} \leftarrow \mathrm{seed}$
for $i = 1, \dots, N$:
if $i \leq M$:
$A_i \leftarrow b_i$
else:
$x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32}$
$r \leftarrow \mathrm{state} \gg 59$
$y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32}$
$A_i \leftarrow y \bmod K$
$\mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}$

Sample 1 Explanation:
In this input, $A = (4,2,4,1)$.

• For $k = 0$, $A' = (4,2,4,1)$, and the number of syllables is $2$.
• For $k = 1$, $A' = (5,3,5,2)$, and the number of syllables is $0$.
• For $k = 2$, $A' = (0,4,0,3)$, and the number of syllables is $1$.
• For $k = 3$, $A' = (1,5,1,4)$, and the number of syllables is $2$.
• For $k = 4$, $A' = (2,0,2,5)$, and the number of syllables is $1$.
• For $k = 5$, $A' = (3,1,3,0)$, and the number of syllables is $2$.

Sample 2 Explanation:
In this input, $A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5)$.

Constraints

• $1 \leq N \leq 7 \times 10^6$
• $1 \leq K \leq 2300$
• $0 \leq A_i \leq K-1$ ($1 \leq i \leq N$)
• $V_j \in {0,1}$ ($0 \leq j \leq K-1$)
• $0 \leq \mathrm{seed} \leq 2^{60} - 1$
• $1 \leq M \leq \min(N, 10^5)$
• $0 \leq b_i \leq K-1$ ($1 \leq i \leq M$)
• All input values are integers.

输入格式

本题的输入采用特殊格式。

不直接给出 $A_1, \dots, A_N$，而是从标准输入中给出整数 $\mathrm{seed}, M, b_1, \dots, b_M$。请使用以下伪代码所表示的计算过程恢复出 $A_1, \dots, A_N$。

其中，伪代码中所有变量均为无符号 64 位整数。$s \oplus t$ 表示 $s$ 与 $t$ 的按位异或（XOR），$s \gg t$ 表示 $\lfloor s / 2^t \rfloor$（右移操作），$s \ll t$ 表示 $s \times 2^t$（左移操作）。

$\mathrm{state} \leftarrow \mathrm{seed}$
for $i = 1, \dots, N$:
if $i \leq M$:
$A_i \leftarrow b_i$
else:
$x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32}$
$r \leftarrow \mathrm{state} \gg 59$
$y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32}$
$A_i \leftarrow y \bmod K$
$\mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}$

样例 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 \leq N \leq 7 \times 10^6$
• $1 \leq K \leq 2300$
• $0 \leq A_i \leq K-1$（$1 \leq i \leq N$）
• $V_j \in \{0,1\}$（$0 \leq j \leq K-1$）
• $0 \leq \mathrm{seed} \leq 2^{60} - 1$
• $1 \leq M \leq \min(N, 10^5)$
• $0 \leq b_i \leq K-1$（$1 \leq i \leq M$）
• 所有输入值均为整数。