E2. 子矩阵游戏（困难版）

时间限制：2 秒
内存限制：256 MB

本题为困难版本。两个版本的区别在于所有变量的约束不同。只有两个版本都通过，才能进行 Hack。

Tsovak 和 Narek 正在玩一个游戏。
他们有一个数组 $a$ 和一个 $n$ 行 $m$ 列的整数矩阵 $b$，行列均从 $1$ 开始编号。第 $i$ 行第 $j$ 列的格子记为 $(i,j)$。

他们轮流按顺序在矩阵中寻找数组 $a$ 中的元素，Tsovak 先手。

• Tsovak 先找 $a_1$，然后 Narek 找 $a_2$，接着 Tsovak 找 $a_3$，以此类推。
• 假设当前玩家选择了一个格子 $(r,c)$，那么下一个玩家必须在子矩阵 $(r+1,c+1)$ 到 $(n,m)$ 中寻找下一个元素（如果 $r=n$ 或 $c=m$，则子矩阵为空）。

如果一名玩家无法找到所需的元素（或者剩余子矩阵为空），或者数组已经结束（上一位玩家已经选择了最后一个元素），那么该玩家输。

你的任务是：在双方都采取最优策略的情况下，判断胜者。

注意：由于输入规模较大，你可能需要优化输入/输出。
例如，在 C++ 中，可以在 main() 函数开头使用以下代码：

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1500$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $l, n, m$（$1 \le l, n, m \le 1500$），分别表示数组 $a$ 的长度以及矩阵的行数和列数。

第二行包含 $l$ 个整数 $a_1, a_2, \dots, a_l$（$1 \le a_i \le n \cdot m$）。

接下来的 $n$ 行，每行包含 $m$ 个整数 $b_{i,1}, b_{i,2}, \dots, b_{i,m}$（$1 \le b_{i,j} \le n \cdot m$），表示矩阵的第 $i$ 行。

数据保证：

• 所有测试用例的 $n \cdot m$ 之和不超过 $3 \times 10^6$。
• 所有测试用例的 $l$ 之和不超过 $1500$。

---

输出格式

对于每个测试用例，输出一行一个字符：

• 若 Tsovak 获胜，输出 "T"；
• 否则输出 "N"（表示 Narek 获胜）。

---

示例

输入

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

输出

N
T
N

---

样例解释

第一个样例：

• Tsovak 需要找 $a_1 = 1$，矩阵中唯一的一个 $1$ 在 $(1,1)$，他只能选这个格子。
• 然后 Narek 需要在子矩阵 $(2,2)$ 到 $(2,3)$ 中找 $a_2 = 2$。该子矩阵包含 $6$ 和 $2$，他选择 $2$。
• 此时数组已经结束，Tsovak 输，故 Narek 获胜。

第二个样例：

• Tsovak 需要找 $1$，他可以选 $(2,4)$ 位置的 $1$（即最后一行最后一列）。
• 这样下一个玩家的子矩阵为空，Narek 无法找 $2$，直接输，因此 Tsovak 获胜。