[THUPC2018] 组合数问题

**友情提示：本题篇幅较长。**

众所周知，小葱同学擅长计算，尤其擅长计算组合数。 于是现在我们有了一个 $N\times M$ 的棋盘，棋盘上有些地方会有障碍物的存在。在棋盘上有 $K$ 枚棋子，每枚棋子要么属于红队要么属于蓝队。此外，每枚棋子有两个属性值，第 $i$ 枚棋子的两个属性记为 $a_i,b_i$ 并且保证 $a_i\geq b_i$。既然有了两支队伍那么小葱同学就要来玩游戏，这个游戏一共有 $R$ 个回合。每个回合内，每枚棋子会按照如下顺序进行游戏： 0. 回合开始，记当前是第 $H$ 回合。若现在为游戏的开始时刻，则 $H=1$。 1. 对于所有能够移动的棋子，沿着自己当前的方向移动一格。每枚棋子的朝向一定是上下左右中的一种。如果棋子发现自己不能移动，即前方格子为棋盘外部或者障碍物，那么则不向前移动，而是将自己的方向旋转一百八十度，即进行向后转的操作（注意此时转了之后棋子这回合内并不会进行移动）。 2. 对于所有棋子，每个棋子都拥有且仅拥有一种技能。此时所有棋子按照编号从小到大依次释放技能，如果不能释放技能则跳过。技能总共分为以下几种： 1. 重锤火花（toolihai）：以自身为中心，制造出绚丽的烟花，令人赏心悦目，无任何效果。 2. 面子之王（faceking）：该棋子充满了面子，所有棋子都要听其号令，使得所有棋子的方向强制向左（逆时针）转九十度。该技能的效果持续时间为永久。 3. 头发掉光（onepunch）：头发掉光之后，王队长变得更强了，使该枚棋子的属性大幅度提升。即若当前棋子 $i$ 的属性为 $\left(a_i,b_i\right)$，属性的提升值为 $v$，那么该棋子的属性则变为 $\left(a_i+v,b_i\right)$。该技能的效果能持续 $l$ 个回合，若当前回合为 $H$，则该技能效果会在第 $H+l$ 回合开始的时候消失。若在技能消失前棋子 $i$ 的属性为 $\left(a_i,b_i\right)$，则技能效果消失后其属性会变为 $\left(\max\left(a_i-v,0\right),\min\left(b_i,\max\left(a_i-v,0\right)\right)\right)$。注意再该技能效果消失前该技能可能被再次释放，则多次释放的技能效果叠加，但技能效果消失的时间分开计算。（详见样例第二组数据） 4. 拉比哩比（rabiribi）：挥动真正的重锤，制造火花，击退前方扇形区域的所有敌方单位。该技能所能影响到的范围为前方大小为 $v$ 的扇形区域，所谓扇形区域可见下图：  从上图我们可以看出，在图的最下方有正在释放技能的棋子，其技能朝向为上，所以其技能方向也为上。则上方的所有区域则为其技能所影响到的扇形区域，该扇形区域大小为 $5$，即 $v=5$。注意到棋盘上某些位置会有障碍物，障碍物的存在会影响到该技能的影响范围。如果一个障碍物存在于技能范围之内，那么以障碍物开始的处于技能范围内的扇形区域也都不会受到技能的影响。如上图可见，所有黑色格子的最下方格子即为障碍物的位置，所有黑色格子即为受到障碍物影响所不能被技能效果影响的格子。 另一方面，击退效果的定义为将受到技能影响效果的棋子沿着技能释放方向强制移动一格，即从图中 $p_2$ 被击退到 $p_3$ 的位置。如果被击退方向是障碍物或者棋盘边界，则按一下规则进行： - 如果下一位置为障碍物，则被击退到该障碍物后面，即从图中的 $p_0$ 击退到 $p_1$。 - 如果下一位置为棋盘外部，如当前在第一行并且要被击退到第零行，则被击退到第 $N$ 行对应的同一列的位置。 重复以上过程直到被击退到一个不是障碍物和棋盘外部的位置，则该击退过程结束。（详见样例第一组数据） 5. 退学花火（firework）：退学之后，有了更多的时间来挖坑。使得上一个释放重锤火花的棋子在接下来 $l$ 回合内无法移动。如果不存在这样的棋子，则使自己在接下来 $l$ 回合内无法移动。 6. 救乌干达（viuganda）：使用vim，拯救阵亡的棋子，复活距离自身最远的阵亡的己方棋子。若己方没有阵亡棋子，则复活对方距离自身最近的阵亡棋子。如果对方也没有阵亡棋子，则什么也不做。我们这里使用的距离为曼哈顿距离，即若第 $i$ 枚棋子处于位置 $\left(x_i,y_i\right)$， 第 $j$ 枚棋子处于位置 $\left(x_j,y_j\right)$，那么此时两枚棋子的距离为 $\left|x_i-x_j\right|+\left|y_i-y_j\right|$。如果同时有多枚棋子距离当前棋子的曼哈顿距离一样，那么我们选择其中编号最大的棋子即可。棋子被复活后如果当前回合可以释放技能并且仍然没有被跳过，则会释放技能。 7. 降维打击（2dsaigao）：利用超时空武器，向自己右前方发射动感光波，使得某个区域内的单位不能释放技能。该动感光波发射之后，遇到棋盘边缘或者障碍物则会发生方向改变的现象，如下图所示：  中间格子为当前棋子所处的位置，其方向向左。每当该光波会进入一个有障碍物的格子或者棋盘边缘的时候，该光波就会改变自己的方向顺时针旋转 $90^\circ$。该光波每从一个格子的中心到达另一个格子的中心时我们称该光波走了 $1$ 的距离。当光波走了 $o$ 的距离之后，光波就会以当前格子为中心发生爆炸，使得所有距离当前格子曼哈顿距离不超过 $v$ 的棋子在接下来 $l$ 回合的时间内都不能释放技能，即从现在到第 $H+l$ 回合开始的这段时间内都不能释放技能。（详见样例第一组数据） 8. 咕咕咕咕（gugugugu）：做人，绝不能普普通通的鸽了别人；要鸽，必须带着大家一起鸽。该技能效果为使得己方所有当前回合还没有释放技能的棋子全部跳过技能释放的环节，即使得己方还未释放技能的棋子当前回合不能释放技能。 9. 反向传播（backward）：让时间暂停，让游戏倒流，让自身回到过去，回到之前的某个回合。若当前为第 $H$ 回合，该技能效果是回到 $l$ 回合前，则当前棋子 $i$ 会回到第 $H-l$ 回合。所谓回到第 $H-l$ 回合，即当前棋子的一下所有值都会变回第 $H-l$ 回合开始的时候的值： - 位置及方向。 - 属性。 - 是否存活以及复活时间。 - 受到的技能影响的效果以及剩余时间。 注意此时棋子 $i$ 的技能刷新时间并不会回到第 $H-l$ 回合的时间。（详见样例第三组数据）（技能刷新时间的规则会在下面说明） 10. 葱之礼赞（hupraise）：葱的到来，使得今天变为了一个神圣的日子，要将红蓝双方的棋子进行配对。每个红方棋子可以和任何一个蓝方棋子进行配对，并且每个棋子都最多只能和对面一个棋子进行配对。第 $i$ 枚棋子 和第 $j$ 枚棋子能够配对的条件为两个棋子属于不同阵营并且 $a_i\oplus a_j$ 是 $3$ 的倍数（该符号为异或）。现在每当该技能发动时，你需要求出最多能够配多少对。 **技能刷新规则**：对于所有技能，当前为第 $H$ 回合，如果第 $i$ 枚棋子释放了技能，那么在第 $H+z_i$ 回合的时候该技能才回复完毕，才能再次释放技能。如果第 $i$ 枚棋子在当前回合中了一个持续时间为 $l$ 回合的技能，那么该技能的影响将在第 $H+l$ 回合开始的时候消除。对于所有棋子，若其首轮技能回复时间为 $f_i$，技能回复时间为 $z_i$，则若没有其他棋子的影响，其第一次将在第 $f_i$ 回合释放技能，之后每 $z_i$ 回合再次释放技能。 3. 对于棋盘上所有格子，如果一个格子内既有红队棋子又有蓝队棋子，那么此时这个格子内的棋子便会发生交战。交战的规则如下： 我们规定第 $i$ 枚棋子的战斗力为 $\binom{a_i}{b_i}$（该式子等价于 $C_{a_i}^{b_i}$）。在交战时，每次由红蓝双方派出己方在这个格子战力最大的棋子进行交战。假设红方派出第 $i$ 枚棋子，蓝方派出第 $j$ 枚棋子。如果红方蓝方两枚棋子战斗力一样，那么派出的两枚棋子均阵亡。若战斗力不一样，假设第 $i$ 枚棋子战力更高，那么第 $j$ 枚棋子阵亡，同时第 $i$ 枚棋子的两个属性变为 $\max\left(a_i-a_j,0\right),\max\left(b_i-a_j,0\right)$。不断重复以上操作直到一方棋子全部阵亡。若第 $i$ 枚棋子在当前回合即第 $H$ 回合阵亡，那么第 $i$ 枚棋子会在第 $H+r_i$ 回合开始的时候复活。第 $i$ 枚棋子复活之后将其两个属性将变为游戏开始时候的属性值，并且移除所有当前棋子身上的技能效果，其移动方向保持阵亡前的移动方向。棋子阵亡期间其技能正常回复，但是不能移动和释放技能，并且不受到其他任何技能的影响。 现在小葱告诉你所有与这游戏相关的东西，希望你按照游戏规则来进行游戏，并输出游戏结束之后每个棋子的位置。

输入包含多组数据，第一行一个整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据： * 第一行四个整数 $N,M,K,R$。 * 接下来 $N$ 行每行 $M$ 个数。对于第 $i$ 行第 $j$ 列的数，如果等于 $0$ 则代表第 $i$ 行第 $j$ 列的格子为普通格子，否则为障碍物。 * 接下来 $K$ 行，每行一开始有九个整数 $x_i,y_i,a_i,b_i,c_i,d_i,f_i,z_i,r_i$。代表第 $i$ 枚棋子一开始的位置位于第 $x_i$ 行 第 $y_i$ 列，其属性值为 $a_i,b_i$ 并且所属的阵营为 $c_i$。如果 $c_i=0$ 则为红方否则为蓝方。棋子 $i$ 一开始的朝向为 $d_i$，$d_i=0,1,2,3$ 分别表示上下左右四个方向。$f_i$ 为技能首轮回复时间，$z_i$ 为技能回复时间，即第 $i$ 枚棋子若在没有受到其他棋子影响的情况下，第一次将在第 $f_i$ 回合释放技能，之后每 $z_i$ 回合再次释放技能。$r_i$ 为其复活时间。接下来一个字符串 $s_i$ 为其技能的英文名字，已在每个技能后面注明了其对应的英文名字。对于不同的技能种类，会在当前行增加一定的输入值，具体如下： 1. 重锤火花（toolihai），无增加的输入。 2. 面子之王（faceking），无增加的输入。 3. 头发掉光（onepunch），增加输入 $v_i,l_i$，代表该技能的增益效果和持续时间。 4. 拉比哩比（rabiribi），增加输入 $v_i$ 代表技能的范围。 5. 平安花火（firework），增加输入 $l_i$ 代表技能的影响时间。 6. 救乌干达（viuganda），无增加的输入。 7. 降维打击（2dsaigao），增加输入 $y_i,v_i,l_i$，代表光波能移动的距离、光波爆炸后能影响的范围以及技能的影响持续时间。 8. 咕咕咕咕（gugugugu），无增加的输入。 9. 反向传播（backward），增加输入 $l_i$，表示回到 $l_i$ 回合之前，数据保证不会回到游戏开始之前。 10. 葱之礼赞（hupraise），无增加的输入。

对于每组数据： * 每当技能 $10$ 发动时，输出一行一个整数。 * 在游戏结束之后，输出 $K$ 行，每行两个整数代表第 $i$ 枚棋子现在处于哪一行哪一列。

4
2 4 4 2
0 0 0 0
0 0 0 1
1 2 1 1 0 2 1 10 1 2dsaigao 1 0 20
2 1 1 1 0 0 1 10 1 faceking
2 1 1 1 0 3 1 10 1 rabiribi 1
1 3 1 1 0 1 1 10 1 toolihai
1 5 4 4
0 0 0 0 0
1 1 2 2 0 3 1 1 100 onepunch 1 2
1 2 1 1 1 0 1 1 100 toolihai
1 3 1 1 1 0 1 1 100 toolihai
1 4 2 1 1 0 1 1 100 toolihai
1 4 1 4
0 0 0 0
1 1 1 1 0 3 3 2 2 backward 2
10 10 10 20
0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 1 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 1 1
0 0 0 0 0 0 0 0 0 1
0 0 1 0 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0
10 9 8 0 0 1 6 7 2 viuganda
5 3 10 0 1 1 6 3 7 toolihai
2 7 6 3 0 3 7 3 1 faceking
5 7 10 9 1 3 9 8 8 rabiribi 10
6 10 1 1 0 1 11 7 7 backward 9
2 3 8 5 0 3 2 9 4 onepunch 6 1
1 7 8 2 0 3 11 2 5 hupraise
9 9 4 3 1 3 12 4 9 gugugugu
2 1 10 6 1 2 6 6 2 2dsaigao 9 9 9
10 10 10 5 1 1 12 4 8 firework 4

1 1
1 1
2 3
2 1
1 4
1 2
1 3
1 4
1 2
5
10 6
2 5
1 5
5 8
6 10
1 7
1 5
8 9
4 9
8 1

### 样例解释 对于第一组数据，在左上方释放技能 $7$ 时，是朝着角落里射出的动感光波，所以碰到角落返回回射出点时，此时距离为 $1$，正好原地爆炸，使得技能 $2$ 无法放出。而右下方是在释放技能 $4$ 时，将对方击穿了地图的例子。 对于第二组数据，第一枚棋子每次向右走一步就会释放一次技能。第一回合走到 $(1,2)$，释放技能后属性变为 $(3,2)$，和对方交战后属性变为 $(2,1)$。第二回合走到 $(1,3)$，释放技能后属性变为 $(3,1)$，和对方交战后属性变为 $(3,0)$。第三回合走到 $(1,4)$，由于之前第一回合释放的技能效果消失，属性变回 $(2,0)$，再重新释放技能变为 $(3,0)$，然后被对手痛殴致死。所以最后停留在了 $(1,4)$。 对于第三组数据，该棋子每走两次就会释放技能跳回两回合前的状态，不断循环这样的过程。 ### 数据范围 保证 $1\leq T\leq 20$，$1\leq N,M\leq 100$，$1\leq K\leq 200$，$1\leq R\leq 1000$。 保证所有的附加输入除了技能 $3,5,7$ 的影响时间大于 $0$ 以外，剩下均大于等于 $0$。 保证棋子一开始不在障碍物上，一开始以及增幅的属性值均不超过 $1000$（但不保证增幅后的属性超过 $1000$） 保证技能的首轮回复时间、之后的回复时间以及复活时间均大于 $0$。 ### 版权信息 来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。 题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。