题目描述

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'$?

输入格式

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}$

输出格式

Output $K$ lines. The $m$-th line ($1 \leq m \leq K$) should contain the answer for $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$)
• All input values are integers.

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

2
0
1
2
1
2

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$.

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

In this input, $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

补充说明

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).

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