* la pasul doi, masina ia cea de-a doua jumatate din cartile pe care le are in zona rezervata si le pune la sfarsitul sirului de carti
* repeta pasul doi pina cind nu mai ramine nicio carte in zona rezervata.

Victoria se intreaba cum va arata sirul de carti dupa $K$ astfel de shuffleuri, asa ca sunteti obligati sa ii oferiti raspunsul!

Victoria se intreaba care este sirul de carti dupa $K$ astfel de shuffleuri, asa ca sunteti obligati sa ii oferiti raspunsul!
 
Pentru a evita fisierele de output foarte mari, sirul obtinut dupa $K$ shuffleuri va fi encodat folosind urmatorul algoritm:
== code(cpp) |
int encode(int N, int S[]) {
    // N = numarul de carti din sir
    // S[i] = cartea care se afla pe pozitia i, (1 <= i <= N)
    int ret = 0;
    for(int i=1; i<=N; i++) {
        ret = (ret * 13 + S[i]) % 1299827;
    }
    return ret; // variabila ret va trebui afisata in fisierul de output
}
==

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $shuffle.out$ se vor afla pe prima linie $N$ numere naturale, separate prin cate un spatiu, reprezentind sirul de carti de pe masa dupa $K$ shuffleuri.

În fişierul de ieşire $shuffle.out$ se va afla pe prima linie un singur numar natural reprezentind sirul de carti de pe masa dupa $K$ shuffleuri, encodat dupa algoritmul prezentat in enunt.

h2. Restricţii si precizari

* $ 2 ≤ N ≤ 1 000 000 $
* $ 0 ≤ K ≤ 1 000 000 000 $

* $2 ≤ N ≤ 2 000 000$
* $0 ≤ K ≤ 10^18^$

* Shuffleul numarul $i$ se efectueaza asupra sirului de carti obtinut in urma primelor $i-1$ shuffleuri, pentru orice $i$ nenul
* Daca un sir de elemente are lungimea $P$, atunci prima jumatate a sirului este reprezentata de primele $[P/2]$ elemente din sir (posibil $0$), restul elementelor constituind cea de-a doua jumatate (adica urmatoarele $P - [P/2]$ elemente)

* $[x]$, unde $x$ este un numar real semnifica partea intreaga a numarului $x$.

* $[x]$, unde $x$ este un numar real semnifica partea intreaga a numarului $x$
* Algoritmul de encodare a sirului nu prezinta nicio particularitate ce ar putea influenta rezolvarea problemei.

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 2
| 823554

|
h3. Explicaţie

...

Initial pe masa se afla sirul de carti $1 2 3 4 5 6 7$. Se efectueaza primul shuffle:
- cea de-a doua jumatate a sirului se muta la inceput, iar prima jumatate se salveaza in zona rezervata. Pe masa vom avea: $4 5 6 7$, iar in zona rezervata: $1 2 3$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $4 5 6 7 2 3$, iar in zona rezervata $1$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $4 5 6 7 2 3 1$, iar in zona rezervata nu vom mai avea nicio carte, deci primul shuffle se termina.
Pe masa se afla sirul $4 5 6 7 2 3 1$ si se incepe efectuarea celui de-al doilea shuffle:
- cea de-a doua jumatate a sirului se muta la inceput, iar prima jumatate se salveaza in zona rezervata. Pe masa vom avea: $7 2 3 1$, iar in zona rezervata: $4 5 6$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $7 2 3 1 5 6$, iar in zona rezervata $4$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $7 2 3 1 5 6 4$, iar in zona rezervata nu vom mai avea nicio carte, deci al doilea shuffle se termina.
Pe masa, la final, se afla sirul $7 2 3 1 5 6 4$, care encodat devine: $823554$.

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

8372