大家期待已久的 BCPC 校赛终于到来了！同学们纷纷排队进入考场，并在考场门口的签到表上签到，同学们的签到方式千奇百怪。
具体来说，签到表是一张 $n \times m$ 的表格，初始每个位置都是 $0$。$q$ 名同学依次进行操作，操作以如下格式给出，设当前操作的同学编号为 $t$：
1 i j x 表示将位置 $(i, j)$ 的值置为 $x$，满足 $1\leq i\leq n,1\leq j\leq m, x \in \{0, 1\}$。2 i 表示将表格的第 $i$ 行各个位置取反（即 $0$ 变成 $1$，$1$ 变成 $0$），满足 $1\leq i\leq n$。3 i 表示将表格的第 $i$ 行按列镜面翻转（即将正着数第 $j$ 个与倒着数第 $j$ 个位置的数交换），满足 $1\leq i\leq n$。4 k 表示将表格的状态恢复到第 $k$ 个人操作之后的状态，满足 $0\leq k < t$。设第 $i$ 个人操作之后，表格中 $1$ 的数量为 $x_i$。负责统计签到人数的 coldwater 的妹子并不关心究竟有多少人来签到了，她只关心下列式子的值：
$$ \left(\sum_{i=1}^{q} {x_i \cdot 813^i}\right) \bmod 100624 $$
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行三个空格隔开的整数 $n, m$ 和 $q$。含义见题目描述。
接下来 $q$ 行，每行依次表示一个同学的操作，格式见题目描述。
数据满足 $1 \leq T \leq 10, 1 \leq n, m \leq 10^3,1 \leq q \leq 2 \times10^5$。
对于每组数据，输出一个整数，表示答案。
1
1 3 5
1 1 1 1
3 1
2 1
1 1 3 1
4 289536$x$ 序列为 $[1, 1, 2, 3, 1]$。