== include(page="template/taskheader" task_id="cosmar") ==
Poveste şi cerinţă...
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':https://infoarena.ro/problema/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.
h2. Date de intrare
Fişierul de intrare $cosmar.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $cosmar.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Exemplu
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 2 * 10^5^$
* $1 ≤ A{~i~}, B{~i~} ≤ 2^30^ - 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^5^$, $A{~i~}, B{~i~} ≤ 2^17^ - 1$.
table(example). |_. cosmar.in |_. cosmar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 2
3
1 6 12
5 0 15
4
2 7 7 8
1 2 8 15
| DA
NU
|
h3. 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$.
== include(page="template/taskfooter" task_id="cosmar") ==
