AT_abc471_g [ABC471G] Caeser Syllables

$ 0 $ から $ K-1 $ までの番号で表される $ K $ 種類の記号があります。 各記号は、母音であるか母音でないかのいずれかです。 $ 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 $ のときの答えを出力せよ。

### 入力の形式 今回の問題の入力は特殊な形式で行われます。 標準入力からは $ A_1, \dots, A_N $ の代わりに整数 $ \mathrm{seed}, M, b_1, \dots, b_M $ が与えられます。 このとき、以下の疑似コードで表される計算によって $ A_1, \dots, A_N $ を復元してください。 なお、疑似コード中の変数はすべて符号なし 64bit 整数であるものとします。 また、 $ s \oplus t $ は $ s,t $ の bitwise 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} $ ### Sample Explanation 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 $ です。 ### Sample Explanation 2 この入力例において $ 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 $ ) - 入力される値はすべて整数