题目描述

汤姆是一只机器人猫，它被展示在一个机器人展览会上，观众是一群热情的年轻人，他们围绕在一个 $m \times n$ 的场地周围。汤姆最初是关闭的，由观众中的一位志愿者将其放置在场地的某个任意位置。在表演开始时（时间零点），通过遥控器将汤姆打开。可怜的汤姆被展示了一个杰瑞的全息幻象，幻象距离它很近，且与它之间的直接路径是水平或垂直的。场地中可能存在障碍物，但幻象总是被放置在汤姆和幻象之间的直接路径上没有障碍物的地方。汤姆试图去抓住杰瑞，但当他到达那里时，幻象会改变位置，追逐继续。我们称每次在一个方向（上、下、左、右）的追逐为一次“追逐行程”。每次行程从上一次幻象消失的地方开始，到下一次幻象出现的地方结束。经过几次追逐行程后，全息幻象不再出现，可怜的汤姆不知道接下来该怎么办。此时，它会收到一个信号，如果它返回到追逐开始的地方，就会发现一只真正的杰瑞正在睡觉，它就可以抓住它。

为了简化问题，我们可以将场地视为一个由方格组成的网格。有些方格被障碍物占据。在任何时刻，汤姆都在网格的某个未被占据的方格中，杰瑞也是如此，并且它们之间的直接路径是水平或垂直的。假设每次汤姆看到幻象时，它都可以通过向四个方向之一移动来到达幻象，而不会碰到障碍物。汤姆通过在网格中移动到相邻的方格来前进，每次只移动一步。

问题是汤姆的记录机制有点模糊，因此每次追逐行程中它所走的步数被记录为一个整数区间，例如向左走了 2 到 5 步。现在轮到你将一个程序发送到汤姆的内存中，帮助它返回起点。但为了简化你在本次比赛中的任务，你的程序只需要计算出汤姆可能开始追逐的所有起始位置的数量。

输入

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量，随后是每个测试用例的输入数据。每个测试用例的第一行包含两个整数 $m$ 和 $n$，分别表示网格的行数和列数（$1 \leq m, n \leq 100$）。接下来是 $m$ 行，每行包含 $n$ 个整数，这些整数要么是 0，要么是 1，表示网格中对应单元格是空的（0）还是被障碍物占据（1）。在场地描述之后，是一系列的行，每行对应汤姆的一次追逐行程（按顺序）。每行包含两个正整数，表示汤姆所走的步数范围（包括两端），后面跟着一个大写字母，表示追逐的方向，方向可以是 R（向右）、L（向左）、U（向上）和 D（向下）四种情况之一。（注意，这些方向是相对于场地的，而不是汤姆转向的方向）。测试用例的这一部分以一行包含两个零的行结束。

输出

对于每个测试用例，应该输出一行，包含一个整数，表示汤姆可能开始追逐的单元格数量。

输入数据 1

2
6 6
0 0 0 0 0 0
0 0 0 1 1 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 1 0 1
0 0 0 0 0 1
1 2 R
1 2 D
1 1 R
0 0
3 4
0 0 0 0
0 0 0 0
0 0 0 0
1 2 R
3 7 U
0 0

输出数据 1

10
0

来源

德黑兰 2001