Fişierul intrare/ieşire:	cosmar.in, cosmar.out	Sursă	InfoPro, Runda 3, Grupa A
Autor	Bogdan Ciobanu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	3.5 sec	Limită de memorie	32000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cosmar

Unii copii, mari amatori de secvenţe, şi-au dorit de Crăciun secvenţa de ultima 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 asa 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 joaca feste şi nu se mai poate încrede într-o simplă egalitate între cele doua ş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 cosmar.in 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

In fişierul de ieşire cosmar.out, 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 * 10⁵
• 1 ≤ A_i, B_i ≤ 2³⁰ - 1
• Pentru 15 puncte, N ≤ 4, A_i, B_i ≤ 15.
• Pentru alte 29 de puncte, N ≤ 500, A_i, B_i ≤ 511
• Pentru alte 36 de puncte, N ≤ 10⁵, A_i, B_i ≤ 2¹⁷ - 1.

Explicaţie

î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.

Cum se trimit solutii?