← 返回题目列表

Codeforces · 2005/E1

E1. Subtangle 游戏(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的差异在于对所有变量的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Tsovak 和 Narek 正在玩游戏。它们有一个数组 $$$a$$$ 和一个整数矩阵 $$$b$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,从 $$$1$$$ 开始编号。第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格为 $$$(i, j)$$$。

他们依次寻找$$$a$$$的元素;佐瓦克首先开始。每次玩家在矩阵中查找包含 $$$a$$$ 当前元素的单元格(Tsovak 查找第一个,然后 Narek 查找第二个,等等)。假设玩家选择了单元格 $$$(r, c)$$$。下一个玩家必须在子矩阵中选择他的单元格,从 $$$(r + 1, c + 1)$$$ 开始,到 $$$(n, m)$$$ 结束(如果 $$$r=n$$$ 或 $$$c=m$$$ ,子矩阵可以为空)。如果玩家找不到这样的单元格(或者剩余的子矩阵为空)或数组结束(前一个玩家选择了最后一个元素),那么他就输了。

您的任务是在玩家发挥最佳的情况下确定获胜者。

输入

输入的第一行包含 $$$t$$$ ($$$1 \le t \le 300$$$) – 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$l$$$、$$$n$$$ 和 $$$m$$$ ($$$1 \le l, n, m \le 300$$$) – 数组的大小和矩阵的大小。

第二行包含 $$$l$$$ 整数 $$$a_1, a_2, a_3, \ldots a_l$$$ ($$$1 \le a_i \le \min(7, n \cdot m)$$$) – 数组 $$$a$$$ 的元素。

最后 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$b_{i,1}, b_{i,2}, b_{i,3}, \ldots b_{i,m}$$$ ($$$1 \le b_{i,j} \le \min(7, n \cdot m)$$$) – 表示矩阵的第 $$$i$$$ 行。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^5$$$。

保证所有测试用例的$$$l$$$总和不超过$$$300$$$。

输出

您应该输出 $$$t$$$ 行,其中第 $$$i$$$ 包含一个代表第 $$$i$$$ 测试用例答案的字符:如果 Tsovak 获胜则为“T”,否则为“N”(不带引号)。

示例

输入 #1

3
2 2 3
1 2
1 3 5
4 5 2
2 2 4
1 2
1 1 3 2
4 2 5 1
2 4 2
1 2
3 4
5 5
5 5
5 5

输出 #1

N
T
N

注意

在第一个示例中,Tsovak 首先查找 $$$1$$$。 $$$1$$$ 在 $$$(1,1)$$$ 处只出现一次,因此他选择了它。然后 Narek 需要在 $$$(2, 2)$$$ 的子矩阵中查找 $$$2$$$,该子矩阵仅包含最后两个元素:$$$5$$$ 和 $$$2$$$。他选择了$$$2$$$,然后Tsovak 输了,因为阵列已经结束。

在第二个示例中,Tsovak 需要选择 $$$1$$$。单元格 $$$(n,m)$$$ 处有一个 $$$1$$$,因此他选择了该单元格。然后,由于 $$$(n + 1, m + 1)$$$ 的子矩阵为空,Narek 找不到 $$$2$$$,所以他输了。