Experimente2

În urma experimentelor făcute în luna în care s-a ținut Olimpiada Județeană de Informatică, Dexter s-a hotărât să-și protejeze cu orice preț descoperirile pe care le-a făcut în legătură cu leacul pentru cancer. Astfel, a ales să implementeze criptarea homomorfică, o metodă aparte care permite efectuarea de operații logice direct pe datele criptate, fără a fi necesară decriptarea lor.

Convins că acest tip de criptare îi va asigura confidențialitatea descoperirilor, Dexter se pregătește să-i trimită, pentru analiză, profesorului său de nanotehnologie cele $Q$ capitole din lucrarea științifică la care lucrează, denumită "Din experimente în experimente". În fiecare dintre aceste capitole, el reprezintă colecția de date experimentale sub forma unui șir de $n$ numere naturale, care pot fi dispuse fie liniar (ca un segment de dreaptă), fie circular (ca un cerc).

Înainte de a trimite datele, Dexter crede că a observat un fenomen neobișnuit în analiza lui de criptare homomorfică: dacă, fie într-o structură liniară, fie într-una circulară, șirul ajunge într-o stare uniformă, adică toate valorile din șir ajung să fie egale (prin înlocuiri succesive de două elemente adiacente cu disjuncția exclusivă (Operație logică notată cu xor, adesea simbolizată prin $\oplus$, iar în C/C++ este reprezentată prin simbolul $\wedge{}$.) a acestora), poate apărea o problemă neprevazută: algoritmii de criptare nu mai pot face diferența între datele criptate, iar calculele directe pe acestea devin nefolositoare.

De exemplu, dacă un capitol este format din $n=4$ numere naturale dispuse liniar, (4, 4, 1, 5) și dacă alegem primele două elemente din șir și le înlocuim cu disjuncția lor exclusivă, vom obține $(4 \oplus 4, 1, 5) = (0,1,5)$. În continuare, oricum am alege două elemente adiacente din șir, nu vom obține un șir în stare uniformă, pentru că
$(0 \oplus 1, 5) = (1,5)$ și $(0, 1 \oplus 5) = (0,4)$.

În schimb, dacă am alege, pentru același șir inițial, ultimele două elemente și le înlocuim cu disjuncția lor exclusivă: $(4, 4, 1\oplus 5) = (4,4,4)$, atunci am obține un șir în stare uniformă.

Cerință

Prin urmare, înainte să trimită lucrarea spre verificare, Dexter trebuie să hotărască, pentru fiecare dintre cele $Q$ capitole, dacă șirul de $n$ numere naturale poate ajunge într-o stare uniformă, cu cel puțin două valori rămase în șir, înlocuind succesiv, de câte ori este nevoie, două elemente adiacente cu disjuncția exclusivă a acestora.

Date de intrare

Fișierul de intrare experimente2.in conține, pe prima linie, două valori:

• $C$, a cărui valoare numerică poate fi 1, dacă valorile se consideră dispuse liniar, sau 2, dacă valorile se consideră dispuse circular;
• $Q$, un număr natural, care indică numărul de capitole pe care Dexter ar vrea să le analizeze.

Pe următoarele linii urmează cele $Q$ capitole, fiecare descris astfel:

• o linie care conține numărul $n$, semnificând numărul de numere din șirul capitolului;
• o linie cu cele $n$ numere naturale, separate prin spații, reprezentând valorile din șir.

Date de ieșire

Fișierul de ieșire experimente2.out va conține, pentru fiecare dintre cele $Q$ capitole, în ordinea în care apar în fișierul de intrare, câte un rând pe care se va afișa fie:

• textul DA, dacă există o succesiune de înlocuiri care face ca șirul la final să aibă minim 2 valori și toate valorile să fie egale;
• textul NU, dacă nu se poate ajunge într-o astfel de situație.

Restricții și precizări

• $2 \leq n \leq 200 \ 000$;
• $1 \leq Q \leq 25$;
• $C \in \{1,2\}$;
• elementele oricărui șir aparțin mulțimii $\{0,1,\dots,2\cdot10^9$};
• suma tuturor numerelor $n$ din toate cele $Q$ capitole nu va depăși $1 \ 000 \ 000$;
• disjuncția exclusivă este o operație logică, supranumită xor.

Exemplul 1

experimente2.in

1 2
6
1 1 0 0 1 1
4
2 4 8 32

experimente2.out

DA
NU

Explicație

Avem $C=1$, deci valorile sunt dispuse liniar. O variantă posibilă este să înlocuim primele și ultimele două elemente cu disjuncția lor exclusivă, astfel obținându-se șirul $(1\oplus1,0,0,1\oplus1)$, adică $(0,0,0,0)$, ceea ce convine.
Pentru șirul $(2, 4, 8, 32)$ nu există nicio variantă de operații prin care am putea ajunge la o stare uniformă.

Exemplul 2

experimente2.in

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

experimente2.out

DA
DA

Explicație

Avem $C=2$, deci valorile sunt dispuse circular. Pentru primul capitol, putem înlocui circular primul și ultimul element, obținându-se șirul $(3\oplus2,1,1,1)$, adică $(1,1,1,1)$.
Pentru al doilea capitol, putem înlocui succesiv primele două elemente, pentru a obține $((1\oplus2)\oplus4,7,7,7)$, adică $(7,7,7,7)$.