CF2005E2.Subtangle Game (Hard Version)

这是该问题的困难版本。两种版本的区别在于所有变量的约束条件。只有当你同时解决了两个版本的问题时，才能进行 Hack。

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

他们轮流在矩阵中寻找 $a$ 的元素；Tsovak 先手。每次轮到某个玩家时，他需要在矩阵中找到当前 $a$ 的元素（Tsovak 先找第一个，Narek 找第二个，依此类推）。假设某位玩家选择了单元格 $(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$），分别表示数组的长度和矩阵的行数、列数。

第二行包含 $l$ 个整数 $a_1, a_2, a_3, \ldots, a_l$（$1 \le a_i \le n \cdot m$），表示数组 $a$ 的元素。

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

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

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

你需要输出 $t$ 行，第 $i$ 行输出一个字符，表示第 $i$ 个测试用例的答案：如果 Tsovak 获胜则输出 "T"，否则输出 "N"（不带引号）。

在第一个样例中，Tsovak 首先寻找 $1$。只有一个 $1$ 出现在 $(1,1)$，所以他选择它。然后 Narek 需要在子矩阵 $(2,2)$ 开始的区域中寻找 $2$，该区域只包含最后两个元素：$6$ 和 $2$。他选择 $2$，此时数组已结束，Tsovak 输了。

在第二个样例中，Tsovak 需要选择 $1$。在单元格 $(n,m)$ 处有一个 $1$，他选择该单元格。此时子矩阵 $(n+1, m+1)$ 为空，Narek 无法找到 $2$，因此他输了。

由 ChatGPT 4.1 翻译