题目描述

有 $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'$ 的音节数是多少？

输入格式

输入从标准输入给出，格式如下：

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

输出格式

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

数据范围

• $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$）
• 所有输入值均为整数。

4 6 12233445577788999 4
4 2 4 1
1 1 0 0 1 0

2
0
1
2
1
2

该输入中 $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$。

15 12 998154573227378904 2
5 6
0 0 1 1 0 1 0 0 1 1 0 1

4
4
3
3
3
4
4
4
3
3
3
4

该输入中 $A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5)$。

7000000 15 409873722375451899 3
7 0 4
1 0 1 1 1 0 1 1 1 0 1 0 1 0 0

1680078
1681239
1679837
1680730
1680470
1679454
1679615
1679371
1681263
1679670
1680218
1680010
1680211
1680521
1681744

补充说明

输入格式

本题的输入以特殊格式给出。

标准输入给出的不是 $A_1, \dots, A_N$，而是整数 $\mathrm{seed}, M, b_1, \dots, b_M$。请按照以下伪代码所表示的计算还原 $A_1, \dots, A_N$。

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

state <- seed

for i = 1, ..., N:
    if i <= M:
        A_i <- b_i
    else:
        x <- (((state >> 18) XOR state) >> 27) mod 2^32
        r <- state >> 59
        y <- ((x >> r) + (x << (32-r))) mod 2^32
        A_i <- y mod K
        state <- (state * 6364136223846793005 + 2026081520260815) mod 2^64

• 来源：AtCoder ABC 471 G

子任务设置

• 子任务 1（180 分）：$N \le 200$，$K \le 30$。
• 子任务 2（180 分）：$N \le 5000$，$K \le 300$。
• 子任务 3（240 分）：无特殊限制（$N \le 7 \times 10^6$，$K \le 2300$）。