Problem Description

The data generator for this problem has been modified, and some solutions will not pass as a result, not due to errors in the solutions themselves!

Little A has a candy tree with $n$ nodes, numbered from $1$ to $n$. Each node contains $m$ children, numbered from $1$ to $m$. Each child can make $k$ wishes, numbered from $1$ to $k$. The $x$-th wish of the $j$-th child in node $i$ can yield $a_{i,j,x}$ candies. We refer to the unmodified candy tree as the $0$-th version tree.

A child is considered happy if the total number of candies they can obtain after $k$ wishes is divisible by $3$, allowing them to evenly distribute the candies among themselves and their parents. That is, the $j$-th child in node $i$ is happy if and only if $\sum_{x=1}^k a_{i,j,x} \bmod 3 = 0$.

A node is considered happy if all $m$ children in that node are happy.

Little A can cast a magic spell: he will make $q$ modifications, indexed from $1$. The $i$-th modification is described as $(x, y, z)$, indicating that in the $x$-th version tree, the number of candies obtained by all children in all nodes for their $y$-th wish is multiplied by $z$, resulting in the $i$-th version tree. You are required to find out how many nodes are happy in each version tree.

Input Format

Due to the large size of the input file, data will be read in an unusual manner.

The first line contains four integers $n$, $m$, $k$, and $X$, representing the number of nodes, the number of children per node, the number of wishes per child, and the random seed, respectively.

The value of $a_{i,j,x}$ is calculated as $(X + X \times i + (X \oplus (j \times x + i \times i))) \bmod 10^9$.

For C++, the implementation is as follows:

a[i][j][x] = (X + 1ll * X * i + (X ^ (1ll * j * x + 1ll * i * i))) % 1000000000;

The next line contains a single positive integer $q$, representing the number of modifications.

For the $i$-th modification, indexed from $1$, $x = (X \oplus i) \bmod i$, $y = (X \oplus i) \bmod k + 1$, and $z = (X + (X \oplus i)) \bmod (10^9 - 1)$, indicating that in the $x$-th version tree, the number of candies obtained by all children in all nodes for their $y$-th wish is multiplied by $z$, resulting in the $i$-th version tree.

For C++, the implementation is as follows:

x = (X ^ i) % i, y = (X ^ i) % k + 1, z = (X + (X ^ i)) % 999999999;

Output Format

Due to the large size of the output file, data will be output in an unusual manner.

Output a single line, representing the XOR sum of the number of happy nodes in the $0$ to $q$ version trees.

Sample Input and Output

Sample Input #1

2 2 3 0
5

Sample Output #1

2

Sample Input #2

100 4 12 1919810
100

Sample Output #2

16

Notes

Sample 1 Explanation:

$a_{1,1,1} = 2$, $a_{1,1,2} = 3$, $a_{1,1,3} = 4$, $a_{1,2,1} = 3$, $a_{1,2,2} = 5$, $a_{1,2,3} = 7$, $a_{2,1,1} = 5$, $a_{2,1,2} = 6$, $a_{2,1,3} = 7$, $a_{2,2,1} = 6$, $a_{2,2,2} = 8$, $a_{2,2,3} = 10$.

After decrypting the modifications:

0 2 1
0 3 2
0 1 3
0 2 4
0 3 5

After decrypting the output:

2
2
2
0
2
2

Data Range:

For $20\%$ of the data, $n \le 10^3$ and $q \le 10^3$.

For $40\%$ of the data, $n \le 10^3$ and $q \le 10^6$.

For another $10\%$ of the data, $m = 1$.

For another $10\%$ of the data, $k = 1$.

For another $5\%$ of the data, $q = 0$.

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 4$, $1 \le k \le 12$, $0 \le q \le 10^6$, $0 \le a_{i,j,x} < 10^9$. For the $i$-th modification, $0 \le x < i$, $1 \le y \le k$, $0 \le z < 10^9 - 1$. $0 \le X \le 10^9$.

见题面 Input 部分

见题面 Output 部分