Cosmar

Unii copii, mari amatori de secvențe, și-au dorit de Crăciun secvența de ultimă generație sir5. Moș Crăciun, angajat DHL, este cel care le va livra, însă le-a încurcat cu alte cadouri din sac (sir5, dar și sistemul sir4 pro), adresate unor copii care nu au fost așa cuminți.

Bătrânul are $T$ cereri, iar pentru fiecare cerere se cunoaște modelul de sir5 așteptat de copil, $A$, și ce vede moșul că are în sanie, $B$. Ambele $A$ și $B$ sunt șiruri de numere naturale. În ultimul timp ochelarii îi joacă feste și nu se mai poate încrede într-o simplă egalitate între cele două șiruri, dar trebuie să treacă prin următorul proces chinuitor:

• Alege un număr natural $K$ și un număr natural $R < 2^K$.
• Pentru toate numerele din secvența $B$ care dau restul $R$ la împărțirea cu $2^K$, le comută bitul $K + 1$ (din valoarea $0$ în $1$ și invers).
• Dacă prin minune a obținut o permutare a șirului A, atunci sărbătorile pentru copilul în cauză sunt salvate și Moșul trece mai departe, altfel poate să reia procesul.

După cum vă așteptați, deja stă de ceva timp pe asta și vă roagă să-i spuneți, pentru fiecare cerere, cât mai repede, dacă poate salva Crăciunul.

Dacă nu era de ajuns, bătrânul vă avertizează că nu are memorie bună și vă sugerează să o verificați înainte să îi rezolvați problema.

Date de intrare

Pe prima linie în fișierul de intrare se găsește numărul de cereri $T$. Fiecare cerere este apoi descrisă în felul următor: pe primia linie se va găsi un număr întreg $N$, reprezentând lungimea șirurilor, pe a doua linie se vor găsi $N$ numere naturale reprezentând șirul $A$, iar pe a treia linie $N$ numere naturale reprezentând șirul $B$.

Date de ieșire

Pentru fiecare cerere, afișați DA dacă Moș Crăciun poate salva sărbătorile și NU, dacă nu.

Restricții

• $1 ≤ T ≤ 10$
• $1 ≤ N ≤ 2 \cdot 10^5$
• $1 ≤ A_i, B_i ≤ 2^{30} − 1$

Subtask 1 (15 puncte)

• $N ≤ 4$
• $A_i, B_i ≤ 15$

Subtask 2 (29 puncte)

• $N ≤ 500$
• $A_i, B_i ≤ 511$

Subtask 3 (36 puncte)

• $N ≤ 10^5$
• $A_i, B_i ≤ 2^{17} − 1$

Subtask 4 (20 puncte)

• Fără restricții suplimentare.

Exemplu

stdin

2
3
1 6 12
5 0 15
4
2 7 7 8
1 2 8 15

stdout

DA
NU

Explicații

În prima cerere, se pot efectua următoarele operații:

• $K = 0, R = 0$, $B$ devine $[4, 1, 14]$.
• $K = 1, R = 0$, $B$ devine $[6, 1, 12]$, care este o permutare a lui $A$.