题目描述

小 A 有一棵糖果树，树上有 $n$ 个节点，编号为 $1,2,\cdots,n$。每个节点里有 $m$ 位小朋友，编号为 $1,2,\cdots,m$。每个小朋友可以进行 $k$ 次祈愿，编号为 $1,2,\cdots,k$。节点 $i$ 中的第 $j$ 位小朋友的第 $x$ 次祈愿可以获得 $a_{i,j,x}$ 个糖果。我们称未被修改的糖果树为第 $0$ 个版本树。

一个小朋友被称为开心的，当且仅当她经过 $k$ 轮祈愿后可以获得的糖果数量可以被 $3$ 整除，这样就可以把糖果平均地分给她和她的父母。也就是说，第 $i$ 个节点的第 $j$ 个小朋友是开心的当且仅当 $\sum_{x=1}^k a_{i,j,x}\bmod 3=0$。

一个节点被称为是快乐的，当且仅当上面的 $m$ 位小朋友都是开心的。

小 A 可以施加魔法：他将会有 $q$ 次修改，下标从 $1$ 开始的第 $i$ 次修改可以描述为 $(x,y,z)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。要求你求出每个版本树中有多少个点是快乐的。

输入格式

由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。

第一行有 $4$ 个整数 $n$、$m$、$k$、$X$，分别表示节点个数、每个节点上的小朋友个数、每个小朋友的祈愿次数、随机种子。

那么 $a_{i,j,x}=(X+X\times i+(X\oplus (j\times x+i\times i))\bmod 10^9$。

对于 C++，代码实现如下：

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

接下来一行一个正整数 $q$，表示修改次数。

对于下标从 $1$ 开始的第 $i$ 次修改，$x=(X\oplus i)\bmod i$，$y=(X\oplus i)\bmod k+1$，$z=(X+(X\oplus i))\bmod (10^9-1)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。

对于 C++，代码实现如下：

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

输出格式

由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。

输出一行，表示第 $0\sim q$ 个版本树中快乐的节点数的异或和。

2 2 3 0
5

2

100 4 12 1919810
100

16

提示

样例 1 解释：

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

对修改解密后为：

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

对输出解密后为：

2
2
2
0
2
2

数据范围：

对于 $20\%$ 的数据，满足 $n\le 10^3$，$q\le 10^3$。

对于 $40\%$ 的数据，满足 $n\le 10^3$，$q\le 10^6$。

对于另外 $10\%$ 的数据，满足 $m=1$。

对于另外 $10\%$ 的数据，满足 $k=1$。

对于另外 $5\%$ 的数据，满足 $q=0$。

对于 $100\%$ 的数据，满足 $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$。对于第 $i$ 次修改，$0\le x<i$，$1\le y\le k$，$0\le z<10^9-1$。$0\le X\le 10^9$。