Problem description

Alicja i Bob grają w grę. Gra odbywa się na szachownicy rozmiaru N × N pól. W każdej kolumnie znajduje się jeden pionek biały oraz jeden czarny. Alicja wykonuje ruchy pionkami białymi, natomiast Bob porusza się czarnymi. Gracze siedzą na przeciwko siebie (oglądają szachownicę z dwóch różnych stron, podobnie jak w grze w szachy lub warcaby). Ruch w grze polega na wybraniu jednego pionka i przesunięciu go o dowolną liczbę pól do przodu lub do tyłu. Zarówno na początku gry, jak i po wykonaniu każdego ruchu musi być jednak spełniony następujący niezmiennik: dla każdej kolumny pionek gracza X musi być bliżej gracza X, niż pionek gracza przeciwnego (niedopuszczalne jest więc przeskoczenie pionka przeciwnika). Gracz, który nie może wykonać ruchu zgodnego z zasadami gry przegrywa.

Alicja zawsze zaczyna. Niestety bardzo często przegrywa – zastanawia się na ile wynika to z jej słabych umiejętności, a na ile z początkowego ustawienia pionków. Mówimy, że gracz posiada strategię wygrywającą jeśli niezależnie od ruchów przeciwnika jest w stanie wygrać (grając optymalnie, zgodnie z zasadami gry).

Napisz program, który: wczyta konfiguracje pionków, obliczy dla każdej konfiguracji czy Alicja posiada strategię wygrywającą i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę plansz, które należy rozważyć. W kolejnych 3Q wierszach znajdują się opisy kolejnych plansz, po trzy wiersze na każdą planszę. Pierwszy wiersz opisu każdej planszy składa się z jednej liczby naturalnej N, określającej rozmiar planszy. Drugi wiersz opisu składa się z N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami i określających pozycje (numery wierszy), w których znajdują się kolejne pionki Alicji (i-ty pionek jest umieszczony w i-tej kolumnie oraz w A_i-tym wierszu). Trzeci wiersz opisu składa się z N liczb naturalnych B_i, pooddzielanych pojedynczymi odstępami i określających pozycje, w których znajdują się kolejne pionki Boba, w formacie analogicznym do opisu pozycji pionków Alicji.

Wyjście

Twój program powinien wypisać na wyjście Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tej planszy. Odpowiedź ta składa się z jednego słowa TAK – jeśli Alicja ma strategię wygrywającą, lub NIE – w przeciwnym przypadku.

Ograniczenia

1 ≤ Q ≤ 15, 2 ≤ N ≤ 100 000, 1 ≤ A_i < B_i ≤ N.

Przykład

2
3
1 1 1
2 2 2
3
2 2 1
3 3 3

NIE
TAK