La un supermarket există două case de marcat la care clienții își pot plăti cumpărăturile. Când intră în magazin, fiecare client primește un număr unic. Când aceștia vor să plătească, se așază la rând la una dintre cele două case. Clienții sunt procesați pe rând, în ordinea venirii lor.

Cerința

Scrieți un program care procesează cozile de la casele de marcat. Acest program primește N instrucțiuni pe care trebuie să le execute. Aceste instrucțiuni pot fi de următoarele 4 tipuri:

• 1 – S-a eliberat casa de marcat numărul 1. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
• 2 – S-a eliberat casa de marcat numărul 2. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
• 3 x – Clientul cu numărul x se așază la coadă la casa la care așteaptă mai puțini clienți; dacă la ambele case așteaptă același număr de clienți, atunci clientul cu numărul x se va așeza la coadă la casa 1; trebuie afișată coada la care se așază clientul x. Se garantează că acest client nu este deja așezat la vreun la rând.
• 4 x – Clientul cu numărul x părăsește rândul la care așteaptă (se garantează că era deja la un rând); în acest caz nu trebuie afișat nimic.

Date de intrare

Fișierul de intrare supermarket.in conţine pe prima linie numărul de instrucțiuni N. Pe fiecare dintre următoarele N linii se află câte o instrucțiune, în forma descrisă la cerinţă.

Date de ieșire

Fișierul de ieșire supermarket.out va conţine rezultatele afişate în urma executării instrucţiunilor din fişierul de intrare, în ordinea din fişier, câte un rezultat pe o linie.

Restricții și precizări

• 4 ≤ N ≤ 100.000
• 1 ≤ x ≤ 1.000.000
• Pentru teste valorând 30 de puncte, 4 ≤ N ≤ 1.000
• Pentru teste valorând 30 de puncte nu vor exista instrucțiuni de tipul 4.
• Un client care a părăsit la un moment dat rândul (fie în urma unei instrucțiuni de tipul 4, fie datorită faptului că a plătit la casă), se poate întoarce și se poate așeza din nou rând (ca și cum ar fi venit prima dată).

Exemplu

supermarket.in

10
3 5
3 21
3 7
2
1
2
3 5
3 8
4 7
1

supermarket.out

1
2
1
21
5
-1
2
1
8

Explicație

Clientul 5 se aşază la rând la casa 1
Clientul 21 se aşază la rând la casa 2
Clientul 7 se aşază la rând la casa 1
La casa 2 intră clientul 21
La casa 1 intră clientul 5
La casa 2 nu este nimeni în așteptare
Clientul 5 se aşază la rând la casa 2
Clientul 8 se aşază la rând la casa 1
Clientul 7 părăseşte rândul (nu se afişează nimic)
La casa 1 intră clientul 8

#include <bits/stdc++.h>
#define VMAX 1000002
#define NMAX 1000002
#define ZMILION 10000000
using namespace std;
ifstream fin("supermarket.in");
ofstream fout("supermarket.out");

int c[2][NMAX];
int unde[VMAX];
int inc[2]={1,1}, sf[2], lg[2];
int n;

int main()
{int i, tip, x, casa;
 fin >> n;
 for (i = 1; i <= n; i++)
     {
      fin >> tip;
      if(tip <= 2)
        {tip--;
         while (inc[tip]<=sf[tip] && unde[c[tip][inc[tip]]]%ZMILION!=inc[tip])
                {inc[tip]++;}
         if (inc[tip]>sf[tip])
            fout << "-1\n";
            else
            {
            fout<<c[tip][inc[tip]]<<'\n';
            inc[tip]++; lg[tip]--;
            }
        }
        else
        {
        fin>>x;
        if (tip == 3)
            {
             casa=0;
             if (lg[1]<lg[0]) casa=1;
             fout<<casa+1<<'\n';
             sf[casa]++; c[casa][sf[casa]]=x;
             unde[x]=sf[casa]+casa*ZMILION;
             lg[casa]++;
            }
            else //4
            {
            casa=unde[x]/ZMILION;
            lg[casa]--;
            unde[x]=0;
            }

       }
     }
 fout.close();
 return 0;
}