Problem Description

Xiao A has a candy tree with $n$ nodes, numbered $1,2,\cdots,n$. In each node, there are $m$ children, numbered $1,2,\cdots,m$. Each child can make $k$ wishes, numbered $1,2,\cdots,k$. For the $x$-th wish of the $j$-th child in node $i$, the child can get $a_{i,j,x}$ candies. We call the candy tree that has not been modified version $0$.

A child is called happy if and only if, after making $k$ rounds of wishes, the total number of candies she can get is divisible by $3$, so that the candies can be evenly shared among her and her 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 called joyful if and only if all the $m$ children in it are happy.

Xiao A can cast magic: he will perform $q$ modifications, indexed from $1$. The $i$-th modification is described by $(x,y,z)$, meaning that in version $x$ of the tree, for all nodes and all children, the number of candies obtained from the $y$-th wish is multiplied by $z$, producing version $i$ of the tree. You are required to output how many nodes are joyful in each version of the tree.

Input Format

The first line contains $3$ integers $n$, $m$, and $k$, representing the number of nodes, the number of children in each node, and the number of wishes per child.

Then read $n$ lines, each containing $m\times k$ integers, representing $a_{i,j,x}$, indexed starting from $1$.

Then one line contains a positive integer $q$, representing the number of modifications.

Then read $q$ lines. The $i$-th line contains three positive integers $x,y,z$, meaning that in version $x$ of the tree, for all nodes and all children, the number of candies obtained from the $y$-th wish is multiplied by $z$, producing version $i$ of the tree, indexed starting from $1$.

Output Format

Output $q+1$ lines, each containing a positive integer. The $i$-th line denotes the number of joyful nodes in version $i-1$ of the tree.

2 2 3
1 2 3 4 5 6
7 8 9 10 11 12
5
0 1 13
0 2 14
1 2 15
1 3 16
2 3 17

2
2
0
0
2
0

10 1 2
568508003 500481779
296073373 42467215
878878423 182698953
810051825 300278778
506619835 300576052
878109763 816209514
722729481 557555287
810227870 524124026
693592304 92818139
971977946 139368888
3
0 1 524124026
0 1 500481779
0 2 816209514

1
6
6
2

Hint

Constraints:

For $0\%$ of the testdata, $n\le 10^3$, $q\le 10^3$.

For $0\%$ of the testdata, $n\le 10^3$, $q\le 10^6$.

For another $0\%$ of the testdata, $m=1$.

For another $0\%$ of the testdata, $k=1$.

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

For $100\%$ of the testdata, $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}\le 10^9$. For the $i$-th modification, $0\le x<i$, $1\le y\le k$, $0\le z\le 10^9$.

The input and output are large, so a fast I/O method is required.

Translated by ChatGPT 5