mstack

Bulănel tocmai a descoperit o problemă interesantă de structuri de date și s-a gândit să o propună la concursul la care voi tocmai participați. Voi trebuie să implementați o structură de date pe care o vom numi MStack, care suportă toate operațiile pe care le suportă o stivă obișnuită (push, pop, top) plus operația middle (care returnează elementul aflat la jumătatea stivei). Deoarece această problemă ar fi fost prea ușoară, Bulănel adaugă urmatoarele restricții: MStack-ul vostru poate folosi ca structură internă de stocare doar $13$ stive obișnuite (numerotate de la $1$ la $13$), iar numărul de operații asupra acestora trebuie să fie mai mic sau egal decât $5 \times$ numărul operațiilor asupra MStack-ului.

Operațiile care vor fi executate asupra MStack-ului sunt:

• push: adaugă valoarea $x$ in vârful MStack-ului, unde $x$ este egal cu numărul de operații push efectuate pâna în momentul curent;
• top: returnează valoarea din vârful MStack-ului;
• middle: returnează valoarea care se află la jumătatea MStack-ului (daca sunt $N$ elemente în stiva, elementul din mijlocul stivei se gasește pe poziția $\frac{N}{2}+1$ numărând de la baza stivei);
• pop: elimină elementul din vârful MStack-ului.

Pentru ca voi să nu trișati, va trebui ca operațiile pe care le efectuați asupra celor $13$ stive să le scrieți în fișierul de ieșire, iar operațiile permise sunt:

• move a b: mută elementul din vârful stivei $a$ în vârful stivei $b$;
• pop a: aruncă elementul din vârful stivei $a$;
• push a: adaugă în vârful stivei $a$ valoarea $x$, unde $x$ este egal cu numărul de operații push efectuate pâna in momentul curent;
• top a: răspunde la operația top sau middle a MStack-ului, adică în vârful stivei $a$ se află elementul din vârful MStack-ului sau din mijlocul MStack-ului.

Cerință

Dându-se un set de operații care vor fi executate asupra MStack-ului, voi trebuie să execuțati o succesiune de operații asupra celor $13$ stive astfel încât:

1. Pentru fiecare operație push sau pop din fișierul de intrare există o singură operatie push sau pop în fișierul de ieșire, păstrând ordinea din fișierul de intrare;
2. Pentru fiecare operatie top si middle din fișierul de intrare există o singură operație top în fișierul de ieșire, păstrând ordinea din fișierul de intrare;
3. La toate operațiile push, top și middle trebuie să se răspundă exact în ordinea din fișierul de intrare
4. Operația move poate fi inserată între oricare două operații.

Date de intrare

Fisierul de intrare mstack.in conține pe prima linie numărul de operații $N$, iar pe urmatoarele $N$ linii vor fi descrise cele $N$ operații, câte una pe linie.

Date de ieșire

Fisierul de iesire mstack.out conține operațiile care vor fi executate asupra celor $13$ stive, câte o operație pe linie, în ordinea în care vor fi executate.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• Pentru $30\%$ din teste $1 \leq N \leq 1 \ 000$
• Se garantează că nu se va efectua nici o operație pop când MStack-ul este gol
• Atenție! Pentru a primi punctajul pe un test, numărul de operații din fișierul de ieșire trebuie sa fie mai mic sau egal cu $5 \times$ numarul de operații din fișierul de intrare.

Exemplu

mstack.in

6
push
push
push
middle
pop
top

mstack.out

push 1
push 2
push 3
top 2
pop 3
top 2

Explicație

Se inserează în MStack elementele $1, 2$ si $3$. Middle are ca rezultat valoarea $2$, apoi se elimina $3$, iar top-ul din urmă are ca rezultat tot valoarea $2$.

Intern, se insereaza in stiva $1$ elementul $1$, in stiva $2$ elementul $2$ si in stiva $3$ elementul $3$. Pentru a obtine middle-ul apelam top-ul stivei $2$. Pentru pop apelam pop-ul stivei $3$, iar pentru ultimul top apelam top-ul stivei $2$.