XQUERY Anh Thái 11.1.2022 VOI22

#define task ""

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
int q;

struct node
{
    int cnt[18], sum;
    node *child[2];

    node()
    {
        memset(cnt, 0, sizeof cnt);
        sum = 0;
        child[0] = child[1] = NULL;
    }
};

struct Trie
{
    const int maxbit = 17;
    node root;
    int _xor;

#define bit(i, x) (((x) >> (i)) & 1)

    Trie()
    {
        _xor = 0;
    }

    void Add(int x)
    {
        int id = maxbit;
        node *a = &root;

        x ^= _xor;

        while (1)
        {
            for (int i = 17; ~i; --i)
                if (bit(i, x))
                    ++a->cnt[i];
            ++a->sum;

            if (id == -1)
                return;

            if (!(a->child[bit(id, x)]))
                a->child[bit(id, x)] = new node;

            a = a->child[bit(id, x)];
            --id;
        }
    }

    bool Del(node *a, int x, int id)
    {
        if (id == -1)
        {
            if (a->sum)
            {
                for (int i = 17; ~i; --i)
                    if (bit(i, x))
                        --a->cnt[i];
                --a->sum;
                return true;
            }
            else
                return false;
        }

        if ((a->child[bit(id, x)]) && Del(a->child[bit(id, x)], x, id - 1))
        {
            for (int i = 17; ~i; --i)
                if (bit(i, x))
                    --a->cnt[i];
            --a->sum;
            return true;
        }

        return false;
    }

    void Delete(int x)
    {
        x ^= _xor;
        Del(&root, x, maxbit);
    }

    ll Get(int k)
    {
        int id = maxbit;
        node *a = &root;
        ll ans(0);

        while (1)
        {
            if (id == -1)
            {
                for (int i = 17; ~i; --i)
                    if (bit(i, _xor))
                        ans += (1ll << i) * min(k, a->sum - a->cnt[i]);
                    else
                        ans += (1ll << i) * min(k, a->cnt[i]);
                break;
            }

            int x = 0, y = 1;

            if (bit(id, _xor))
                swap(x, y);

            if ((a->child[x]) && a->child[x]->sum >= k)
                a = a->child[x];
            else
            {
                if (a->child[x])
                {
                    k -= a->child[x]->sum;

                    for (int i = 17; ~i; --i)
                        if (bit(i, _xor))
                            ans += (1ll << i) * (a->child[x]->sum - a->child[x]->cnt[i]);
                        else
                            ans += (1ll << i) * a->child[x]->cnt[i];
                }

                a = a->child[y];
            }

            --id;
        }
        return ans;
    }
} f;

void Read()
{
    cin >> q;
}

void Solve()
{
    while (q--)
    {
        int t, x;
        cin >> t >> x;
        if (t == 0)
            f.Add(x);
        else if (t == 1)
            f.Delete(x);
        else if (t == 2)
            f._xor ^= x;
        else
            cout << f.Get(x) << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}