#include <bits/stdc++.h>
#include "long.h"
using namespace std;

struct sethash {
    int val;
    void encode();
    void decode();
    void operator=(int x);
};

struct infoset {
    sethash sum;
    int sz;
    int size()const {
        return sz;
    }
};

extern const infoset emptyset;
infoset merge(const infoset &a, const infoset &b);
void report(infoset p);
void init(int id, int n, int q, vector<int>dad, vector<infoset>ve);
void modify(int x, int y);
void ask(int x, int y);

namespace Min_25 {
typedef unsigned ui;

inline void upa(ui &a, ui b) {
    a < b ? a = b : 0;
}

mt19937 R(114514);
const int N(1e5 + 5), B(300);
int n, q, i, j, dad[N];
infoset val[N];
ui prio[N];

struct node {
    int ch[2], fa, sz, qsz, sz2;
    ui p;
    infoset ss, ts;
} t[N];

inline bool nrt(int x) {
    return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x;
}

inline void rupd(int x) {
    if (t[x].sz2 <= B) {
        int o = t[t[x].ch[1]].ss.size() < t[t[x].ch[0]].ss.size();
        t[x].ts = merge(t[t[x].ch[o]].ss, val[x]);
        t[x].ss = merge(t[t[x].ch[!o]].ss, t[x].ts);
    }
}

vector<pair<int, int>>vec;

inline void upd(int x) {
    t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + 1;
    t[x].sz2 = t[t[x].ch[0]].sz2 + t[t[x].ch[1]].sz2 + t[x].qsz + 1;
    vec.push_back({0, x});
}

inline int dir(int x, int y) {
    return t[x].ch[1] == y;
}

inline void rotate(int x) {
    int y = t[x].fa, z = t[y].fa, o = dir(y, x);

    if (nrt(y))
        t[z].ch[dir(z, y)] = x;

    t[x].fa = z;
    t[y].ch[o] = t[x].ch[!o];
    t[t[x].ch[!o]].fa = y;
    t[x].ch[!o] = y;
    t[y].fa = x;
    upd(y);
}

inline void uprot(int x) {
    for (; nrt(x) && t[x].p > t[t[x].fa].p; rotate(x))
        ;
}

inline void downrot(int x) {
    int a, b;

    for (;;)
        if (max(t[a = t[x].ch[0]].p, t[b = t[x].ch[1]].p) > t[x].p)
            rotate(t[a].p > t[b].p ? a : b);
        else
            break;
}

set<pair<ui, int>>se[N];
inline int getrt(int x) {
    for (; nrt(x); x = t[x].fa)
        ;

    return x;
}

inline int go(int x, int o) {
    for (; t[x].ch[o]; x = t[x].ch[o])
        ;

    return x;
}

inline int getdep(int x) {
    int d = 0;

    for (; x; x = t[x].fa)
        ++d;

    return d;
}

inline int getrk(int x) {
    int rk = t[t[x].ch[0]].sz + 1, y;

    for (; nrt(x);)
        y = t[x].fa, rk += t[y].ch[1] == x ? t[t[y].ch[0]].sz + 1 : 0, x = y;

    return rk;
}

inline ui getmx(int x) {
    ui ret = t[t[x].ch[1]].p;
    int y;

    for (; nrt(x);)
        y = t[x].fa, upa(ret, x == t[y].ch[0] ? t[y].p : 0), x = y;

    return ret;
}

void split(int x, int &L, int &R, int tp) {
    if (tp == 0)
        L = x, R = t[x].ch[1], t[R].fa = t[L].ch[1] = 0;
    else
        L = t[x].ch[0], R = x, t[L].fa = t[R].ch[0] = 0;

    for (; nrt(x);) {
        int y = t[x].fa;

        if (t[y].ch[1] == x)
            t[y].ch[1] = L, t[L].fa = y, L = y;
        else
            t[y].ch[0] = R, t[R].fa = y, R = y;

        x = y;
    }

    t[L].fa = t[R].fa = 0;
}

int merge(int x, int y) {
    if (!x || !y)
        return x | y;

    if (t[x].p > t[y].p)
        return t[t[x].ch[1] = merge(t[x].ch[1], y)].fa = x, x;
    else
        return t[t[y].ch[0] = merge(x, t[y].ch[0])].fa = y, y;
}

inline ui Mx(int x) {
    return se[x].empty() ? 0 : se[x].rbegin()->first;
}

inline void mdf(int x, int y, int o) {
    if (o == 1)
        se[x].insert({t[y].p, y});
    else
        se[x].erase({t[y].p, y});
    t[x].qsz += t[y].sz2 * o;
    t[x].p = max(prio[x], Mx(x));
}

inline void modify(int x, int y) {
    vec.clear();
    dad[x] = y;
    int p, q, a, b, c = 0, d, e, f, ox = x, s;
    f = getrt(x);
    a = t[f].fa;

    if (a)
        mdf(a, f, -1);

    split(x, p, q, 1);
    b = go(p, 1);

    for (; b; b = d) {
        for (c = b; d = t[c].fa, d && Mx(d) <= max(Mx(b), t[c].p); c = d);

        t[d].ch[1] = 0;

        if (!se[b].empty())
            e = se[b].rbegin()->second, mdf(b, e, -1), downrot(b), c = merge(getrt(c), e), t[c].fa = 0;

        for (; upd(b), b != c; b = t[b].fa);

        t[c].fa = d;

        if (d)
            mdf(d, c, 1);
    }

    if (c)
        t[c].fa = a;

    if (a && c)
        mdf(a, c, 1);

    if (a)
        downrot(a);

    for (s = 0, e = x; e; e = t[e].fa)
        s += t[t[e].ch[1]].sz2 + t[e].qsz + 1;

    for (; a; a = t[a].fa) {
        if (t[a].fa && !nrt(a))
            t[t[a].fa].qsz -= s;

        upd(a);
    }

    for (; upd(x), nrt(x); x = t[x].fa);

    t[x].fa = y;

    for (; a = t[x].fa, a && getmx(a) < t[x].p;) {
        b = getrt(a);
        c = t[b].fa;

        if (c)
            mdf(c, b, -1);

        split(a, p, q, 0);

        if (q) {
            for (b = go(q, 0); upd(b), b != q; b = t[b].fa);

            t[q].fa = a, mdf(a, q, 1), uprot(a);

            if (t[a].p > t[p].p)
                p = a;
        }

        b = go(p, 1);
        x = merge(p, x);
        t[x].fa = c;

        for (; upd(b), nrt(b); b = t[b].fa);
    }

    if (a)
        mdf(a, x, 1), uprot(a);

    for (; a; a = t[a].fa) {
        if (t[a].fa && !nrt(a))
            t[t[a].fa].qsz += s;

        upd(a);
    }

    for (auto &u : vec)
        u.first = -getdep(u.second);

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (auto u : vec)
        rupd(u.second);
}

void ask(int u, int l, int r) {
    int A = t[t[u].ch[0]].sz;

    if (t[u].sz2 <= B && l == 1 && r == t[u].sz) {
        report(t[u].ss);
        return;
    }

    if (l <= A + 1 && A + 1 <= r)
        report(val[u]);

    if (l <= A)
        ask(t[u].ch[0], l, min(r, A));

    if (A + 1 < r)
        ask(t[u].ch[1], max(1, l - A - 1), max(1, r - A - 1));
}

inline void ask(int x, int y) {
    for (;;) {
        int tx = getrt(x), ty = getrt(y), rx = getrk(x), ry = getrk(y);

        if (tx == ty) {
            if (rx > ry)
                rx ^= ry ^= rx ^= ry;

            ask(tx, rx, ry);
            break;
        } else {
            if (getdep(tx) < getdep(ty))
                x ^= y ^= x ^= y, tx ^= ty ^= tx ^= ty, rx ^= ry ^= rx ^= ry;

            ask(tx, 1, rx);
            x = t[tx].fa;
        }
    }
}

vector<int> e[N];
ui mx[N];
int ma[N];

void dfs1(int x) {
    mx[x] = t[x].p = prio[x] = R();
    t[x].sz = 1;

    for (int y : e[x]) {
        dfs1(y);
        upa(mx[x], mx[y]);

        if (mx[y] >= mx[ma[x]])
            ma[x] = y;
    }

    for (int y : e[x])
        if (y ^ ma[x])
            upa(t[x].p, mx[y]);
}

void dfs2(int x) {
    if (ma[x])
        dfs2(ma[x]);

    for (int y : e[x])
        if (y != ma[x])
            dfs2(y);

    if (x > 1 && x == ma[dad[x]])
        return;

    static int st[N];
    int w = 0, ox = x;

    for (; x; x = ma[x])
        st[++w] = x;

    function<int(int, int)>dfs = [&](int l, int r) {
        if (l == r) {
            t[st[l]].sz = 1;
            t[st[l]].sz2 = t[st[l]].qsz + 1;
            t[st[l]].ss = val[st[l]];
            return st[l];
        }

        int m = l;

        for (int i = l; i <= r; ++i)
            if (t[st[i]].p > t[st[m]].p)
                m = i;

        if (l < m)
            t[t[st[m]].ch[0] = dfs(l, m - 1)].fa = st[m];

        if (m < r)
            t[t[st[m]].ch[1] = dfs(m + 1, r)].fa = st[m];

        upd(st[m]);
        return st[m];
    };
    int rt = dfs(1, w);
    x = ox;

    if (x > 1)
        se[t[rt].fa = dad[x]].insert(make_pair(t[rt].p, rt)), t[t[rt].fa].qsz += t[rt].sz2;
}

inline void init(int nn, int qq, vector<int>dadd, vector<infoset>vee) {
    n = nn;
    q = qq;

    for (i = 2; i <= n; ++i)
        e[dad[i] = dadd[i - 2]].push_back(i);

    for (i = 1; i <= n; ++i)
        val[i] = vee[i - 1];

    dfs1(1);
    t[0].ss = emptyset;
    dfs2(1);

    for (auto &u : vec)
        u.first = -getdep(u.second);

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (auto u : vec)
        rupd(u.second);
}
}

void init(int id, int n, int q, vector<int>dad, vector<infoset>ve) {
    Min_25::init(n, q, dad, ve);
}

void modify(int x, int y) {
    Min_25::modify(x, y);
}

void ask(int x, int y) {
    Min_25::ask(x, y);
}

answer.code:5:8: error: redefinition of ‘struct sethash’
    5 | struct sethash {
      |        ^~~~~~~
In file included from answer.code:2:
long.h:6:8: note: previous definition of ‘struct sethash’
    6 | struct sethash{
      |        ^~~~~~~
answer.code:12:8: error: redefinition of ‘struct infoset’
   12 | struct infoset {
      |        ^~~~~~~
In file included from answer.code:2:
long.h:26:8: note: previous definition of ‘struct infoset’
   26 | struct infoset{
      |        ^~~~~~~