Candy Tree Happiness

You are given a candy tree with n nodes numbered \(1,2,\dots,n\). In each node, there are m children numbered \(1,2,\dots,m\). Each child makes \(k\) wishes, numbered \(1,2,\dots,k\). In node \(i\), the \(j\)th child obtains \(a_{i,j,x}\) candies from the \(x\)th wish. The original (unmodified) candy tree is called version \(0\).

A child is considered happy if and only if, after all \(k\) wishes, the total number of candies she receives is divisible by 3. In other words, 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 of its m children are happy.

Small A can cast magic to modify the candy tree. There will be q modifications. The \(i\)th modification (\(i \ge 1\)) is described by three integers \((x, y, z)\), meaning that starting from version \(x\) of the tree, for every node and every child, the number of candies obtained from the yth wish is multiplied by \(z\) (in modulo 3 arithmetic). The resulting tree becomes version \(i\).

Your task is to determine, for each version of the candy tree (including version \(0\) and all modified versions), how many nodes are happy.

Note: Since all operations are regarded modulo 3, you only need to care about values mod 3. All formulas in this problem are in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) \( (1 \le n, m, k \le \text{small limits})\), representing the number of nodes, kids per node, and number of wishes respectively.

The following \(n \times m\) lines describe the candy tree. For each node from \(1\) to \(n\), there are m lines. Each line contains \(k\) integers, where the \(x\)th integer represents \(a_{i,j,x}\) --- the number of candies for the \(x\)th wish for that child.

The next line contains a single integer \(q\) \( (q \ge 2)\), the number of modifications.

Each of the next \(q\) lines contains three integers \(x, y, z\). The \(i\)th modification is applied on version \(x\) of the tree, and it multiplies the candies from the \(y\)th wish by \(z\) for every child in every node, resulting in version \(i\). You may assume \(0 \le x < i\) and \(1 \le y \le k\).

outputFormat

Output \(q+1\) lines. The \(i\)th line (starting from \(i=0\)) should contain a single integer representing the number of happy nodes in version \(i\) of the candy tree.

sample

1 1 1
3
1
0 1 2

1
1