Cerința

Se consideră două șiruri:

• A=(A[1],A[2],...,A[N]) format din N numere naturale distincte;
• C=(C[1],C[2],...,C[N]) format din N cifre din mulțimea {1,2} și C[1] = 1, denumit șir cod.

Prin reașezarea numerelor din șirul A pe baza codului C se obține un nou șir B ce conține toate numerele din A. Procedeul de reașezare folosit, denumit codificare, este următorul:

• inițial, se așează primul număr A[1] din șirul A pe prima poziție din șirul B
• se parcurge șirul A de la al doilea element către al N-lea, iar fiecare element A[K] (2 ≤ K ≤ N) se așează:
  • la începutul șirului B, dacă C[K] = 1
  • la sfârșitul șirului B, dacă C[K] = 2

De exemplu, pentru N = 4, A = (34,9,3,56), C = (1,1,2,1) se obține șirul codificat B = (56,9,34,3).

Cerința

1. Pentru N dat și un șir C cu N elemente, verificați dacă C poate fi un șir cod.
2. Pentru N dat, un șir A cu N elemente și șir C un șir cod cu N, determinați șirul B obținut prin codificarea de mai sus.
3. Pentru N dat și două șiruri A și B cu câte N elemente, determinați șirul cod prin care șirul A a fost codificat și s-a obținut șirul B.

Date de intrare

Fișierul de intrare coddecod.in conține pe prima linie, un număr natural c (1, 2 sau 3) reprezentând cerința care trebuie rezolvată:

• Dacă c = 1, conține pe linia a doua un număr natural N, iar pe linia a treia conține N numere naturale, separate prin câte un spațiu, reprezentând elementele unui șir X;
• Dacă c = 2, conține pe linia a doua numărul natural N, pe linia a treia conține N numere naturale distincte, separate prin câte un spațiu, reprezentând elementele șirului A, iar pe linia a patra conține N numere naturale, separate prin câte un spațiu, reprezentând elementele șirului cod C, cu semnificația din enunț;
• Dacă c = 3, conține pe linia a doua numărul natural N, pe linia a treia conține N numere naturale distincte, separate prin câte un spațiu, reprezentând elementele șirului A, iar pe linia a patra conține N numere naturale distincte, separate prin câte un spațiu, reprezentând elementele șirului B, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire coddecod.out conține o singură linie, pe care este scris răspunsul la cerința de rezolvat:

• dacă c = 1, răspunsul DA dacă șirul X poate fi un șir cod; în caz contrar, conține răspunsul NU (răspunsul la cerința 1);
• dacă c = 2, N numere naturale, separate prin câte un spațiu, reprezentând șirul B determinat (răspunsul la cerința 2);
• dacă c = 3, N numere naturale, separate prin câte un spațiu, reprezentând șirul cod C determinat (răspunsul la cerința 3).

Restricții și precizări

• 1 ≤ N ≤ 10000
• 0 ≤ A[K], B[K], X[K] ≤ 32000 pentru K = 1,2,3,...N
• Pentru fiecare A și B date, există un singur șir cod C pentru obținerea șirului B prin codificarea șirului A

Exemplul 1:

coddecod.in

1
4
1 5 0 7

coddecod.out

NU

Explicație

Se rezolvă cerința 1. N=4. Șirul X=(1, 5, 0, 7) nu poate fi un șir cod.

Exemplul 2:

coddecod.in

1
7
1 2 1 2 1 2 2

coddecod.out

DA

Explicație

Se rezolvă cerința 1. N=7. Șirul X=(1, 2, 1, 2, 1, 2, 2) poate fi un șir cod.

Exemplul 3:

coddecod.in

2
6
37 1 56 2 989 12
1 1 2 1 2 1

coddecod.out

12 2 1 37 56 989 

Explicație

Se rezolvă cerința 2. N=6, A=(37, 1, 56, 2, 989, 12), C=(1, 1, 2, 1, 2, 1). Șirul determinat este B=(12, 2, 1, 37, 56, 989)

Exemplul 4:

coddecod.in

2
5
9 5 17 3 6
3 5 9 17 6

coddecod.out

1 1 2 1 2

Explicație

Se rezolvă cerința 2. N=5, A=(9, 5, 17, 3, 6), B=(3, 5, 9, 17, 6) Șirul cod determinat este C=(1, 1, 2, 1, 2)