Problem Statement

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

Input

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}

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.

Input

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

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