#include <bits/stdc++.h>
using namespace std;
void op1(int x, int y); void op2(int k);
struct Initializer { template<typename Fp> Initializer(Fp f) { f(); } };

const int N = 4e6 + 7, H = 10, LEAF_OFS = 4e6;
struct Node { int fa, sz; vector<int> son; };
struct PreNode { int l, r, pl, pm, pr; };
int ins_v, nd_c = H + 1; Node nd[N]; PreNode pre[N];

Initializer __initializer([]() { for(int i = 1; \
    i <= H; ++i) { nd[i].son = {i + 1}, nd[i + 1].fa = i; } });
inline void Ins(int x, int y = 0) { op1(x, y ? y : ins_v); }
inline int Leaf() { int x = LEAF_OFS + ins_v; return Ins(x), x; }
inline int Val(int u, int w) { return u << (w << 1); }
inline int Siz(int u) { return u > LEAF_OFS ? 1 : nd[u].sz; }

int Get(int x, int k, int w) {
    if(!w) return nd[x].son[k] - LEAF_OFS;
    for(const int s : nd[x].son)
        if(k >= nd[s].sz) k -= nd[s].sz;
        else return Get(s, k, w - 1);
}
void Insert(int x, int k, int w) {
    auto &[fa, sz, son] = nd[x];
    if(!w) son.insert(son.begin() + k, Leaf());
    else if(!k) Insert(son[0], k, w - 1);
    else { int K = k; for(const int s : son)
        if(K > nd[s].sz) K -= nd[s].sz;
        else { Insert(s, K, w - 1); break; } }
    
    Ins(x); if(++sz <= Val(3, w)) return;
    auto &[l, r, pl, pm, pr] = pre[x]; int lst = 4;
    if(!pm) { l = ++nd_c, r = ++nd_c;
        for(const int s : son) if((pm += Siz(s)) > Val(1, w)) break; }
    else if(k <= pm) ++pm, k < pl && (Ins(l), ++pl, --lst);
    else if(k < pm + pr) Ins(r), ++pr, --lst;
    while(lst && pl < pm) Ins(l, Get(x, pl++, w)), --lst;
    while(lst) Ins(r, Get(x, pm + pr++, w)), --lst;
    auto iit = son.begin(); int tst = pm;
    while(tst) tst -= Siz(*iit++);
    if(sz != Val(4, w)) return; auto &z = nd[fa].son;
    auto it = son.begin(); while(pm) pm -= Siz(*it++);
    nd[l] = {fa, pl, vector<int>(son.begin(), it)};
    nd[r] = {fa, pr, vector<int>(it, son.end())};
    auto jt = find(z.begin(), z.end(), x);
    *jt = r, z.insert(jt, l); if(!w) return;
    for(auto p = son.begin(); p != it; ++p) nd[*p].fa = l;
    for(auto p = it; p != son.end(); ++p) nd[*p].fa = r;
}
void Qry(int x, int l, int r, int w, int z = 0) {
    if(l <= z && z + Siz(x) <= r) return op2(x);
    if(l >= z + Siz(x) || r <= z) return;
    for(int s : nd[x].son) Qry(s, l, r, w - 1, z), z += Siz(s);
}
void solve(int x, int l, int r)
    { ++ins_v, Insert(1, --x, H), Qry(1, --l, r, H); }