E2. Игра Подугольник (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Разница между двумя версиями заключается в ограничениях на переменные. Вы можете делать взломы, только если решены обе версии задачи.

Цовак и Нарек играют в игру. У них есть массив $$$a$$$ и матрица целых чисел $$$b$$$ с $$$n$$$ строками и $$$m$$$ столбцами, пронумерованных с $$$1$$$. Ячейка в $$$i$$$-й строке и $$$j$$$-м столбце обозначается $$$(i, j)$$$.

Они ищут элементы $$$a$$$ по очереди; первым начинает Цовак. Каждый раз игрок ищет в матрице клетку, содержащую текущий элемент $$$a$$$ (Цовак ищет первый, Нарек — второй и т.д.). Допустим, игрок выбрал клетку $$$(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$$$.

В $$$i$$$-й из последующих $$$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 \cdot 10^6$$$.

Гарантируется, что сумма $$$l$$$ по всем наборам входных данных не превосходит $$$1500$$$.

Выходные данные

Вы должны вывести $$$t$$$ строк, $$$i$$$-я из которых содержит символ, представляющий ответ на $$$i$$$-й набор входных данных: «T», если победил Цовак, или «N», в противном случае (без кавычек).

Пример
Входные данные
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
Примечание

В первом наборе входных данных Цовак начинает с поиска $$$1$$$. Существует только одно вхождение $$$1$$$ в $$$(1,1)$$$, поэтому он выбирает его. Затем Нареку нужно найти $$$2$$$ в подматрице $$$(2, 2)$$$, которая состоит только из двух последних элементов: $$$6$$$ и $$$2$$$. Он выбирает $$$2$$$, и Цовак проигрывает, так как массив закончился.

Во втором наборе входных данных Цовак должен выбрать $$$1$$$. В клетке $$$(n,m)$$$ есть $$$1$$$, поэтому он выбирает эту клетку. Затем, поскольку подматрица $$$(n + 1, m + 1)$$$ пуста, Нарек не может найти $$$2$$$, поэтому он проигрывает.