SUPCOM (Duyên hải 11 2019)

#define task "SUPCOM"

#include <iostream>
#include <cstdio>

using namespace std;

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

constexpr int N = 1e5 + 5;
template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

template <class T>
void readsign(T &x)
{
    x = 0;
    register int c, neg = 0;
    while ((c = getchar()) && (c > '9' || c < '0'))
        if (c == '-')
            neg = 1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (neg)
        x = -x;
}
constexpr int lift = 1e9 + 1;

struct node
{
    int v;
    ll sum;
    node *child[2];
    node()
    {
        child[0] = child[1] = NULL;
        sum = v = 0;
    }
};

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

struct Trie
{
    node beg;
    void Add(int v)
    {
        int x = v + lift,
            id = 30;
        node *a = &beg;

        while (1)
        {
            if (id == -1)
            {
                a->sum += v;
                ++(a->v);
                return;
            }

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

            a->sum += v;
            ++(a->v);

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

            --id;
        }
    }

    ll Get(int x)
    {
        ll ans(0);
        int id(30);
        node *a = &beg;

        while (1)
        {
            if (id == -1)
            {
                ans += a->sum;
                break;
            }

            if (bit(id, x))
            {
                if (a->child[0])
                    ans += a->child[0]->sum;
                if (!(a->child[1]))
                    break;
                a = a->child[1];
            }
            else
            {
                if (!(a->child[0]))
                    break;
                a = a->child[0];
            }
            --id;
        }

        return ans;
    }

    ll Query2(int a, int b)
    {
        return Get(b + lift) - Get(a - 1 + lift);
    }

    ll Gets(int z)
    {
        int id(30);
        node *a = &beg;

        ll ans(0);

        while (1)
        {

            if (id == -1)
            {
                ans += (a->v == 0 ? 0 : (a->sum) / (a->v) * z);
                break;
            }

            if (a->child[0] && a->child[0]->v >= z)
                a = a->child[0];
            else
            {
                if (a->child[0])
                {
                    ans += a->child[0]->sum;
                    z -= a->child[0]->v;
                }
                a = a->child[1];
            }

            --id;
        }

        return ans;
    }

    int Find(int z)
    {
        int id(30);
        node *a = &beg;

        int ans(0);

        while (1)
        {
            if (id == -1)
                break;

            if (a->child[0] && a->child[0]->v >= z)
            {
                a = a->child[0];
                ans = ans * 2;
            }
            else
            {
                ans = ans * 2 + 1;
                if (a->child[0])
                    z -= a->child[0]->v;
                a = a->child[1];
            }

            --id;
        }

        return ans - lift;
    }

    ll Query3(int l, int r)
    {
        ll ans = Gets(r) - Gets(l - 1);

        int x = Find(r),
            y = Find(l);

        Add(x - 1);
        Add(y + 1);

        return ans;
    }
} f;

int n;

void Read()
{
    //cin >> n;
    read(n);
}

void Solve()
{
    while (n--)
    {
        int t;
        //cin >> t;
        read(t);

        if (t == 1)
        {
            int v;
            //cin >> v;
            readsign(v);
            f.Add(v);
        }
        else
        {
            int a, b;
            //cin >> a >> b;
            readsign(a);
            readsign(b);
            if (t == 2)
                cout << f.Query2(a, b) << "\n";
            else
                cout << f.Query3(a, b) << "\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();
}