시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 2048 MB433100.000%

문제

W przedszkolu Bajtosi jest dużo zabawek i czasami ciężko dziewczynce zdecydować, którą z nich będzie się bawić danego dnia. W celu ułatwienia sobie wyboru, Bajtosia postanowiła użyć wyliczanek.

Jeśli danego dnia chce wybrać jedną z $n$ zabawek, to ustawia je wszystkie w rzędzie i numeruje od $1$ do $n$. Zaczyna od wskazania na jedną z zabawek, a potem recytuje wyliczankę i przy każdej sylabie przechodzi do zabawki poprzedniej lub następnej w rzędzie (w przypadku zabawki $1$ oraz $n$ nie ma wyboru i musi przejść odpowiednio do $2$ oraz $n - 1$). Ostatnią wskazaną zabawką bawi się przez resztę dnia.

Bajtosia w trakcie wyliczanki śledzi, ile razy wskazuje na każdą z zabawek: po skończeniu wyliczanki zabawka $i$-ta została wskazana $a_i$ razy. Sprawdź, czy Bajtosia się nie pomyliła, czyli dla danego ciągu $a_1, a_2, \dots , a_n$ zapamiętanego przez Bajtosię stwierdź, czy istnieje wyliczanka do niego pasująca.

Sytuacja ta powtarzała się przez $t$ dni z różnymi podzbiorami zabawek $i$ różnymi wyliczankami.

입력

Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 ≤ t ≤ 100\, 000$), oznaczającą liczbę dni, w których Bajtosia używała wyliczanek do wyboru zabawki. Następnie jest $t$ opisów poszczególnych dni, jeden za drugim.

Pierwszy wiersz opisu dnia zawiera jedną liczbę całkowitą $n$ ($1 ≤ n ≤ 1\, 000\, 000$), oznaczającą liczbę zabawek uczestniczących tego dnia w wyliczance. Drugi wiersz zawiera ciąg $n$ liczb całkowitych $a_1, a_2, \dots , a_n$ ($0 ≤ a_i ≤ 10^9$), oznaczających ile razy kolejne zabawki zostały wskazane w trakcie wyliczanki według Bajtosi. Możesz założyć, że co najmniej jedna z liczb $a_i$ jest niezerowa.

Suma wszystkich wartości $n$ po wszystkich $t$ dniach nie przekracza $1\, 000\, 000$.

출력

Na wyjście należy wypisać $t$ wierszy zawierających jedno ze słów TAK lub NIE. Słowo TAK oznacza, że istnieje wyliczanka pasująca do ciągu zapamiętanego przez Bajtosię, słowo NIE oznacza, że taka wyliczanka nie istnieje.

예제 입력 1

7
3
1 3 1
2
5 7
3
0 1 0
1
2
6
3 3 2 1 0 0
5
1 3 2 2 3
3
1 0 1

예제 출력 1

TAK
NIE
TAK
NIE
TAK
NIE
NIE

노트

Pierwszego dnia Bajtosia w trakcie wyliczanki mogła wskazywać kolejno przedmioty $2$, $1$, $2$, $3$, $2$.

Trzeciego dnia użyła krótkiej wyliczanki i zaczęła bawić się pierwszą wskazaną zabawką.

Natomiast piątego mogła wskazać kolejno przedmioty $1$, $2$, $3$, $4$, $3$, $2$, $1$, $2$, $1$.

Dla żadnego z pozostałych dni nie istnieje odpowiednia wyliczanka.