Ruirui 和 Doc 正在一个有 $n$ 行 $m$ 列的棋盘上玩一个有趣的游戏。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。棋盘上有一些破损的格子，棋子无法进入。首先，Doc 给 Ruirui 一个指令序列，每条指令属于以下四种形式之一：

• Move Up：从格子 $(x, y)$ 移动到格子 $(x - 1, y)$；
• Move Down：从格子 $(x, y)$ 移动到格子 $(x + 1, y)$；
• Move Left：从格子 $(x, y)$ 移动到格子 $(x, y - 1)$；
• Move Right：从格子 $(x, y)$ 移动到格子 $(x, y + 1)$。

然后，Ruirui 将一枚棋子放在棋盘上的某个格子里。Ruirui 会按照 Doc 的指令序列移动棋子。如果棋子在移动后会移出棋盘边界或进入破损的格子，她会忽略该指令，并继续考虑下一条指令，直到最后一条指令。现在，Ruirui 想要找出棋子最终所在的格子。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含 4 个整数 $n, m, o$ 和 $l$ ($1 \le n, m, o, l \le 1000$)，分别表示行数、列数、破损格子的数量以及 Doc 的指令序列长度。

接下来的 $o$ 行，每行包含两个整数 $i$ 和 $j$，描述一个破损格子的位置。

最后一行包含 Doc 的指令序列，这是一个长度为 $l$ 的字符串，每个字符为 {"U", "D", "L", "R"} 中的一个，分别表示向上移动、向下移动、向左移动和向右移动。

输出格式

对于每个测试用例，对于每一个未破损的格子 $(i, j)$，假设棋子从 $(i, j)$ 开始，最终停在 $(x(i, j), y(i, j))$，输出所有未破损格子 $(i, j)$ 的 $(i - x(i, j))^2 + (j - y(i, j))^2$ 之和。

样例

输入 1

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

输出 1

Case #1: 49
Case #2: 241