游戏在一张长n行宽m列的网格形棋盘上进行，棋子落在网格的交叉点上，我们不妨记左上角的交叉点的坐标为(1,1)，右下角的交叉点坐标为(n,m)。
棋子分为黑白两色，对局双方各执一方棋子。
每个棋子除了颜色以外还有等级，不妨设coli 为棋子i的颜色，lvi 为棋子i的等级。另外，棋盘上的网格线共有4种状态，对于第 ii 条网格线，设其状态为opti。
轮到每方下棋时，他可以选择棋盘上的一个己方棋子沿网格线进行移动到另一个交叉点，称为走子。形式化定义走子的过程如下：选择一个坐标序列 (x0,y0),(x1,y1),…,(xk,yk)，其中k是任意选定的正整数，(x0,y0) 是棋子初始的位置，(xk,yk) 是棋子最终走到的位置，需要满足：
需要注意的是，由上述定义可以得出，不允许棋子在吃子后继续向前走。
网格线的状态含义如下所述：
同时规定在一次走子过程中，棋子经过的网格线的状态必须全部相同，比如从(1,1)经过直行道路走到(1,2)再经过互通道路走到(1,3)是不允许的。
至于如何判断胜负等其它细节，与本题无关，故略去。
小 z 和小 c 开发出这款棋类游戏后，为了提升水平，想了一个训练的策略：一开始棋盘是空的，然后小 c 会每次往棋盘的某个空交叉点上放一枚棋子，小 z 需要快速计算出：若选择这枚新放上的棋子进行一次走子，棋盘上一共有多少个位置是能被走到的？注意：因为这只是思维训练，他们并不会真的走这枚棋子。
可怜的小 z 发现他的计算力不足以算出这个问题，只好向你求助。
每个测试点由多组数据组成。
第一行：一个正整数T表示数据组数。
对于每组数据：
第一行：三个正整数n, m, q，分别表示棋盘的行数、列数和游戏的轮数。
接下来n行，每行为一个长m−1的字符串，每个字符为0、1、2、3 中的一个，第i行第j个字符表示交叉点 (i,j) 连向交叉点(i,j+1) 的网格线状态。
接下来n−1行，每行为一个长m的字符串，每个字符为0、1、2、3 中的一个，第i行第j个字符表示交叉点(i,j)连向交叉点(i+1,j) 的网格线状态。
接下来q行，每行4个非负整数coli,lvi,xi,yi，表示在第i轮有一枚颜色为coli，等级为lvi 的棋子放在了交叉点(xi,yi) 上。其中coli=0 表示黑子，coli=1 表示白子。保证之前交叉点(xi,yi)上没有棋子。
1
3 3 5
13
22
23
010
233
0 1 2 3
1 2 2 1
1 3 1 2
0 2 3 2
1 3 2 2
4
3
3
3
2
【样例解释 #1】
放置棋子1后，它能走到的位置为(2,1),(2,2),(3,2),(3,3)。
放置棋子2后，它能走到的位置为(2,2),(2,3),(3,1)。
放置棋子3后，它能走到的位置为(1,1),(1,3),(2,2)。
放置棋子4后，它能走到的位置为(2,2),(3,1),(3,3)。
放置棋子5后，它能走到的位置为(2,3),(3,2)。
【数据范围】
| 测试点编号 | n×m≤ | q≤ | 特殊性质 |
|---|---|---|---|
| 1∼2 | 100 | 50 | 无 |
| 3∼6 | 5000 | 2000 | 无 |
| 7∼8 | 2×105 | 105 | 不存在“直行道路”与“互通道路” |
| 9∼11 | 2×105 | 105 | 不存在“互通道路” |
| 12∼14 | 2×105 | 105 | 不存在“直行道路” |
| 15∼16 | 2×105 | 105 | lvi=i |
| 17∼18 | 2×105 | 105 | vi=q−i+1 |
| 19∼21 | 2×105 | 2000 | n,m≤1000 |
| 22∼25 |
2×105 |
105 | 无 |
对于100% 的数据，1≤T≤5，2≤n,m≤105，4≤n×m≤2×105，1≤q≤min{105,n×m}，1≤lvi≤q，1≤xi≤n，1≤yi≤m，coli∈{0,1}。
注：由于本题输入输出规模较大，建议使用较为快速的输入输出方式。