题目描述

小 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$ 个版本树。要求你求出每个版本树中有多少个点是快乐的。

输入格式

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

接下来读入 $n$ 行，每行 $m\times k$ 个整数，表示 $a_{i,j,x}$，从 $1$ 开始标号。

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

接下来读入 $q$ 行，第 $i$ 行三个正整数 $x,y,z$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树，从 $1$ 开始标号。

输出格式

输出 $q+1$ 行，每行一个正整数，第 $i$ 行表示第 $i-1$ 个版本树中快乐的节点数。

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

提示

数据范围：

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

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

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

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

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

输入输出量较大，需要快速输入输出算法。