#include <fstream>
#include <iostream>
#include <vector>
#include <time.h>
#include <cstdlib>
#include <typeinfo>


using namespace std;

/*------------------------------------------------------*/

// Clasa de Baza ->

class Hash_Base
{

    public:

    void generate_random();

    virtual int hash_function1(int&) = 0;
    virtual int hash_function2(int&) = 0;

    virtual bool insert (int) = 0;
    virtual bool erase (int) = 0;
    virtual bool find (int) = 0;

    virtual void operator *= (int&) = 0;
    virtual void operator /= (int&) = 0;
    virtual bool operator %= (int&) = 0;

    Hash_Base& operator * (int&);
    Hash_Base& operator / (int&);
    Hash_Base& operator % (int&);


    int a1,b1,a2,b2,prim;
    int * table1;
    int * table2;
    int hash_size;

    vector < pair <int,bool> > *operations;

};

Hash_Base&  Hash_Base::operator* (int& value)
{
    *this *= value;
    return *this;
}


Hash_Base&  Hash_Base::operator/ (int& value)
{
    *this /= value;
    return *this;
}


Hash_Base&  Hash_Base::operator% (int& value)
{
    cout << (*this %= value);
    return *this;
}

void Hash_Base::generate_random()
{
    a1 = rand() % hash_size;
    a2 = rand() % hash_size;
    b1 = rand() % hash_size;
    b2 = rand() % hash_size;
}

/*--------------------------------------------------------*/

// Cuckoo Hash pentru Int32 ->

class Hash_Integer : public Hash_Base
{

    int hash_function1(int&);
    int hash_function2(int&);

    public:
    bool insert(int);
    bool erase(int);
    bool find(int);

    Hash_Integer(int size)
    {
        table1 = new int[size];
        table2 = new int[size];
        prim = 1000000009;
        operations = new vector < pair<int,bool> >;

        fill(table1 , table1 + size , 0);
        fill(table2 , table2 + size , 0);
        srand(time(NULL));
        hash_size = size;
        generate_random();
    }

    void operator *= (int&);
    void operator /= (int&);
    bool operator %= (int&);
};

int Hash_Integer::hash_function1(int & value)
{
    return (((long long)a1 + (long long)value * (long long)b1 ) % (long long)prim) % (long long)hash_size;
}

int Hash_Integer::hash_function2(int & value)
{
    return (((long long)a2 + (long long)value * (long long)b2 ) % (long long)prim) % (long long)hash_size;
}

bool Hash_Integer::erase(int value)
{
    int h1 = hash_function1(*(int*)value);
    int h2 = hash_function2(*(int*)value);

    if (table1[h1] != 0 &&*(int*)table1[h1] == *(int*)value)
    {
        table1[h1] = 0;
        return true;
    }

    if (table2[h2] !=0 && *(int*)table2[h2] == *(int*)value)
    {
        table2[h2] = 0;
        return true;
    }

    return false;
}

bool Hash_Integer::find(int value)
{

    int h1 = hash_function1(*(int*)value);
    int h2 = hash_function2(*(int*)value);

    if (table1[h1] != 0 &&*(int*)table1[h1] == *(int*)value)
    {
        return true;
    }

    if (table2[h2] != 0 && *(int*)table2[h2] == *(int*)value)
    {
        return true;
    }

    return false;

}

bool Hash_Integer::insert(int value)
{
    if (find(value)) return true;
    char which = 1;

    for (int i =0;i<30;i++)
    {
        int h1 = hash_function1(*(int*)value);
        int h2 = hash_function2(*(int*)value);
        if (table1[h1] == 0)
        {
            table1[h1] = value;
            return true;
        }
        else if(table2[h2] == 0)
        {
            table2[h2] = value;
            return true;
        }
        else
        {
            if (which == 1)
            {
                swap(value,table1[h1]);
            }
            else
            {
                swap(value,table2[h2]);
            }
            which = - which;
        }
    }
    return false;
}

void Hash_Integer::operator/= (int &value)
{
    int * locatie_noua = new int(value);
    operations -> push_back(make_pair((int)locatie_noua,false));
    int* adress = locatie_noua;
    erase((int)adress);
}

bool Hash_Integer::operator%= (int & value)
{
    return find((int)&value);
}

void Hash_Integer::operator*=(int & value)
{
    int * locatie_noua = new int (value);
    operations -> push_back(make_pair((int)locatie_noua,true));
    int* adress = locatie_noua;

    if (insert((int)adress) == false)
    {
        generate_random();
        fill(table1 , table1 + hash_size , 0);
        fill(table2 , table2 + hash_size , 0);
        bool ok = false;
        while (ok == false)
        {
            ok = true;
            for (int i =0;i<operations -> size();i++)
            {
                bool op = (*operations)[i].second;
                int adress_data = (*operations)[i].first;
                if (op)
                {
                    if (!insert(adress_data))
                    {
                        ok = false;
                        break;
                    }
                }
                else
                {
                    erase(adress_data);
                }
            }
        }
    }
}


int main()
{
    Hash_Base *t = new Hash_Integer(900001);
    ifstream input("hashuri.in");
    ofstream output("hashuri.out");
    int n;
    input >> n;
    for (int i =0;i<n;i++)
    {
        int op , x;
        input >> op >> x;
        if (op == 1)
        {
            *t *= x;
        }
        if (op == 2)
        {
            *t /= x;
        }
        if (op == 3)
        {
            output << (*t %= x) << "\n";
        }
    }
    /*
    int x = 3;
    *t * x % x / x % x / x / x % x * x / x * x % x;
    */

    return 0;
}