supermarket_of

#include <fstream>
#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;
}