== include(page="template/taskheader" task_id="ghemotoace") ==

Alex a cumpărat pentru pisica sa $n$ ghemotoace de culori diferite. În fiecare zi $i$ din următoarele $t$, pisica va alege $q{~i~}$ perechi de ghemotoace adiacente cu care să se joace şi va interschimba poziţiile gheotoacelor din fiecare pereche. Alex ştie culorile ghemotoacelor care au fost interschimbate, dar nu şi ordinea în care s-au realizat interschimbările. Astfel el vă cere să găsiţi ordinea în care se află ghemotoacele în fiecare zi.

Alex a cumpărat pentru pisica sa $n$ ghemotoace de culori diferite pe care le sortează după culoare. În următoarele $t$ zile pisica va alege q perechi de ghemotoace adiacente cu care să se joace şi va interschimba poziţiile gheotoacelor din fiecare pereche. Alex ştie culorile ghemotoacelor care au fost interschimbate dar nu şi ordinea acestora. Astfel el vă cere să găsiţi ordinea în care se află ghemotoacele în fiecare zi.

Culorile sunt codificate prin numere naturale de la $1$ la $n$. Iniţial, ghemotoacele sunt sortate crescător după acest indice al culorii.
 
Răspunsul pentru fiecare zi va fi dat sub forma unui cod reţinut într-o variabilă de tip **unsigned long long** şi obţinut din următoarea formulă:  <tex>\sum_{i=0}^{n-1} 23^{n-1-i}*v[i] modulo 2^{64}^</tex>, unde $v[i]$ înseamnă culoarea ghemotocului de pe poziţia $i$.

Culorile sunt codificate prin numere naturale de la 1 la n.
Răspunsul pentru fiecare zi va fi dat sub forma unui cod reţinut într-o variabilă de tip **unsigned long long** şi obţinut din următoarea formulă:  <tex>\sum_{i=0}^{n-1} 23^{n-1-i}*v[i]</tex> ( $v[i]$ = culoarea ghemotocului de pe poziţia $i$ )

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $ghemotoace.out$ se vor afla $t$ numere, câte unul pe fiecare linie. Pe linia $i$ se va găsi răspunsul pentru ziua $i$.
 
h2. Notă
 
Între ataşamente, puteţi găsi fişierul _$manager.cpp$_ pe care îl puteţi descărca. E recomandat, atât pentru a scrie o sursa eficientă şi elegantă, cât şi pentru a simula experienţa problemei din timpul concursului, să completaţi această sursă cu implementarea funcţiilor $init()$ si $makeSwaps()$.

În fişierul de ieşire $ghemotoace.out$ se vor afla $t$ numere, câte unul pe fiecare linie. Pe linia $i$ se va gasi răspunsul pentru ziua $i$.

h2. Restricţii

* Orice pereche (neordonată) de culori apare cel mult o singură dată în cadrul unei zile. Pentru orice pereche $(a, b)$ se garantează că $a != b$, iar ordinea în care sunt date culorile în pereche este aleatorie.
* Punctarea se va face separat, testele fiind independente unul de altul. Punctajele pe subtaskuri diferă de cele din concurs.

* Orice pereche de culori apare o singură dată în fişierul de intrare.
* Punctarea se va face separat, testele fiind independente unul de altul.

* Primul test ( $nrTestCase = 1$ ) are proprietatea ca perechile sunt date în ordinea în care s-au efectuat interschimbările

* Următoarele 2 teste respectă următoarele restricţii: $1 ≤ n ≤ 20.000$ şi $t = 1$

* Următoarele 2 teste respectă următoarele restricţii: $1 ≤ n ≤ 20.000$  şi $t = 1$

* Următoarele 3 teste respectă următoarele restricţii: $1 ≤ n, t, q{~i~} ≤ 50$
* Următoarele 4 teste respectă următoarele restricţii: $1 ≤ n, t ≤ 20.000$
* <tex> \sum_{i=1}^t q_i \le 1.000.000 </tex> pentru toate testele

h2. Exemplu
table(example). |_. ghemotoace.in |_. ghemotoace.out |

|4 2 2

| 3 1 1

2
1 2
1 3

4
4 3
2 4
3 2
1 4
| 25948
50302

| 1128

|
h3. Explicaţie

$N = 4$
$nrTestCase = 2$
$t = 2$
 
Pentru prima zi:
 
$[1, 2, 3, 4] -> [2, 1, 3, 4] -> [2, 3, 1, 4]$
 
Observaţi că secvenţa $[1, 2, 3, 4] -> [3, 1, 2, 4] -> [3, 2, 1, 4]$ este greşită deoarece elementele $1$ şi $3$ nu sunt adiacente când sunt interschimbate.
 
$25948 = 23^3^ * 3 + 23^2^ * 3 + 23^1^ * 1 + 23^0^ * 4$
 
Pentru a doua zi:
 
$[2, 3, 1, 4] -> [2, 3, 4, 1] -> [2, 4, 3, 1] -> [4, 2, 3, 1] -> [4, 3, 2, 1]$
 
$50302 = 23^3^ * 4 + 23^2^ * 3 + 23^1^ * 2 + 23^0^ * 1$

$[1, 2, 3] -> [2, 1, 3] -> [2, 3, 1]$
$1228 = 23^2^ * 2 + 23^1^ * 3 + 23^0^ * 1$

== include(page="template/taskfooter" task_id="ghemotoace") ==