template<typename T> struct seg {
    struct node {
        node* ch[2];
        char d;
        T v;

        T mi;

        node(int d_, T v_, T val) : d(d_), v(v_) {
            ch[0] = ch[1] = NULL;
            mi = val;
        }
        node(node* x) : d(x->d), v(x->v), mi(x->mi) {
            ch[0] = x->ch[0], ch[1] = x->ch[1];
        }
        void update() {
            mi = numeric_limits<T>::max();
            for (int i = 0; i < 2; i++) if (ch[i])
                mi = min(mi, ch[i]->mi);
        }
    };

    node* root;
    char n;

    seg() : root(NULL), n(0) {}
    ~seg() {
        std::vector<node*> q = {root};
        while (q.size()) {
            node* x = q.back(); q.pop_back();
            if (!x) continue;
            q.push_back(x->ch[0]), q.push_back(x->ch[1]);
            delete x;
        }
    }

    char msb(T v, char l, char r) { // msb in range (l, r]
        for (char i = r; i > l; i--) if (v>>i&1) return i;
        return -1;
    }
    void cut(node* at, T v, char i) {
        char d = msb(v ^ at->v, at->d, i);
        if (d == -1) return; // no need to split
        node* nxt = new node(at);
        at->ch[v>>d&1] = NULL;
        at->ch[!(v>>d&1)] = nxt;
        at->d = d;
    }

    node* update(node* at, T idx, T val, char i) {
        if (!at) return new node(-1, idx, val);
        cut(at, idx, i);
        if (at->d == -1) { // leaf
            at->mi = val;
            return at;
        }
        bool dir = idx>>at->d&1;
        at->ch[dir] = update(at->ch[dir], idx, val, at->d-1);
        at->update();
        return at;
    }
    void update(T idx, T val) {
        while (idx>>n) n++;
        root = update(root, idx, val, n-1);
    }

    T query(node* at, T a, T b, T l, T r, char i) {
        if (!at or b < l or r < a) return numeric_limits<T>::max();
        if (a <= l and r <= b) return at->mi;
        T m = l + (r-l)/2;
        if (at->d < i) {
            if ((at->v>>i&1) == 0) return query(at, a, b, l, m, i-1);
            else return query(at, a, b, m+1, r, i-1);
        }
        return min(query(at->ch[0], a, b, l, m, i-1), query(at->ch[1], a, b, m+1, r, i-1));
    }
    T query(T l, T r) { return query(root, l, r, 0, (1<<n)-1, n-1); }
};