AT_abc471_g [ABC471G] 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' $ ?

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. $$ \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} $$ 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). 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 $ .

### Sample Explanation 1 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 Explanation 2 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.