// This Code was made by Chinese_zjc_.
template <class T>
struct array
{
    std::vector<T> f, g;
    array(long long n) : f(int(std::sqrt(n)) + 5), g(int(std::sqrt(n)) + 5) {}
    T &operator[](const long long &x) { return x * x <= n ? f[x] : g[n / x]; }
};
std::vector<long long> p;
bool isnp[100005];
void work(long long n)
{
    for (int i = 2; i <= 100000; ++i)
    {
        if (!isnp[i])
            p.push_back(i);
        for (auto j : p)
        {
            if (i * j > 100000)
                break;
            isnp[i * j] = true;
            if (i % j == 0)
                break;
        }
    }
    std::vector<long long> pos;
    for (long long i = 1; i * i <= n; ++i)
        pos.push_back(i), pos.push_back(n / i);
    std::sort(pos.begin(), pos.end());
    pos.erase(std::unique(pos.begin(), pos.end()), pos.end());
    array<std::vector<mint>> primes(n);
    auto getprimes = [&](long long x, int y)
    {
        if (p[y] > x)
            return mint(1);
        return y < int(primes[x].size()) ? primes[x][y] : primes[x].back() + (primes[x].size() - 1) - y;
    };
    for (auto i : pos)
    {
        primes[i].push_back(i);
        for (int j = 0; p[j] * p[j] <= i; ++j)
            primes[i].push_back(primes[i][j] - getprimes(i / p[j], j));
    }
    array<std::vector<mint>> dp;
    auto getdp = [&](long long x, int y)
    {
        return y < int(dp[x].size()) ? dp[x][y] : (getprimes(x, y) - 1) * val(1) + val(0);
    };
    for (auto i : pos)
    {
        dp[i].resize(primes[i].size());
        dp[i].back() = (primes[i].back() - 1) * val(1) + val(0);
        for (int j = dp[i].size() - 1; j--;)
            for (long long k = 0, l = 1; l <= i; ++k, l *= p[j])
                dp[i][j] += getdp(i / l, j + 1) * val(k);
    }
    return dp[n][0];
}

void build(int pos){
    scanf("%s",s+1);
    int len=strlen(s+1);
    int now=0;
    for (int i=1;i<=len;i++){
        if (a[now].son[s[i]-'a']==0)a[now].son[s[i]-'a']=++cnt;
        now=a[now].son[s[i]-'a'];
        if (i==len)a[now].pos.push_back(pos);
    }
    return;
}
int head,tail,q[200005];
void getfail(){
    head=1,tail=0;
    for (int i=0;i<26;i++)
        if (a[0].son[i])q[++tail]=a[0].son[i];
    while(head<=tail){
        int now=q[head];
        head++;
        for (int i=0;i<26;i++){
            if (a[now].son[i]){
                a[a[now].son[i]].fail=a[a[now].fail].son[i];
                q[++tail]=a[now].son[i];
            }
            else a[now].son[i]=a[a[now].fail].son[i];
        }
    }
    return;
}
void work(){
    int now=0;
    for (int i=1;i<=n;i++){
        now=a[now].son[s[i]-'a'];
        size[now]++;
    }
    return;
}
void dfs(int now){
    for (int i=first[now];i;i=nxt[i]){
        dfs(v[i]);
        size[now]+=size[v[i]];
    }
    for (int len=a[now].pos.size(),j=0;j<len;j++)
        ans[a[now].pos[j]]+=size[now];
    return;
}

for (int i=2;i<=m;i++){
    if (i<=r)z[i]=min(z[i-l+1],r-i+1);
    while(i+z[i]<=m&&b[i+z[i]]==b[z[i]+1])z[i]++;
    if (i+z[i]-1>r)l=i,r=i+z[i]-1;
}

n=strlen(x+1);
a[++len]='$';
for (int i=1;i<=n;i++)a[++len]=x[i],a[++len]='$';
int l=0,r=0;
for (int i=1;i<=len;i++){
    if (i<=r)mc[i]=min(r-i+1,mc[l+r-i]);
    while(i-mc[i]>=1&&i+mc[i]<=len&&a[i-mc[i]]==a[i+mc[i]])mc[i]++;
    if (i+mc[i]-1>=r)l=i-mc[i]+1,r=i+mc[i]-1;
    lt[i]=(i-mc[i]+2)/2,rt[i]=(i+mc[i]-2)/2;
    ans=max(ans,rt[i]-lt[i]+1);
}

struct pam_node{
    int son[27],len,link,ans;
    pam_node(){
        memset(son,0,sizeof(son));
        len=link=0;
        return;
    }
}pam[1000005];
int cnt;
int n,ans;
char s[1000005];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    cnt=1;
    pam[0].len=-1,pam[0].link=-1;
    pam[1].len=0,pam[1].link=0;
    int last=0;
    for (int i=1;i<=n;i++){        
        s[i]=(s[i]-97+ans)%26+97;
        int p=last;
        while(p!=-1&&s[i]!=s[i-1-pam[p].len])p=pam[p].link;
        if (pam[p].son[s[i]-'a']!=0){
            int now=pam[p].son[s[i]-'a'];
            last=now;
        }
        else{
            int now=++cnt;
            pam[now].len=pam[p].len+2;
            pam[p].son[s[i]-'a']=now;
            last=now;
            int qwq=pam[p].link;
            while(qwq!=-1&&s[i]!=s[i-1-pam[qwq].len])qwq=pam[qwq].link;
            if (qwq==-1)pam[now].link=1;
            else pam[now].link=pam[qwq].son[s[i]-'a'];
        }
        pam[last].ans=pam[pam[last].link].ans+1;
        ans=pam[last].ans;
        printf("%d ",ans);
    }
    return 0;
}

int sam_ins(char x){
    int p=last;
    int now=++sam_cnt;
    sam[now].len=sam[p].len+1;
    while(p!=-1&&sam[p].son[x-'a']==0){
        sam[p].son[x-'a']=now;
        p=sam[p].link;
    }
    if (p==-1){
        sam[now].link=0;
        last=now;
        return now;
    }
    int q=sam[p].son[x-'a'];
    if (sam[q].len==sam[p].len+1){
        sam[now].link=q;
        last=now;
        return now;
    }
    int clone=++sam_cnt;
    sam[clone]=sam[q];
    sam[clone].len=sam[p].len+1;
    sam[now].link=sam[q].link=clone;
    while(p!=-1&&sam[p].son[x-'a']==q){
        sam[p].son[x-'a']=clone;
        p=sam[p].link;
    }
    last=now;
    return now;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
void SAIS(int *s, int *sa, int n, int m)
{
    static const bool S = false, L = true;
    bool t[n];
    t[n - 1] = S;
    for (int i = n - 1; i--;)
        if (s[i] < s[i + 1])
            t[i] = S;
        else if (s[i] > s[i + 1])
            t[i] = L;
        else
            t[i] = t[i + 1];
    auto lms = [&](const int &x)
    { return x > 0 && t[x - 1] == L && t[x] == S; };
    auto equal = [&](int A, int B)
    {
        do
        {
            if (s[A] != s[B] || t[A] != t[B])
                return false;
            ++A;
            ++B;
        } while (!(lms(A) || lms(B)));
        return s[A] == s[B] && t[A] == t[B];
    };
    std::vector<int> g;
    for (int i = 0; i != n; ++i)
        if (lms(i))
            g.push_back(i);
    int sum[m + 1], *p[m];
    std::fill(sum, sum + m + 1, 0);
    for (int i = 0; i != n; ++i)
        ++sum[s[i] + 1];
    for (int i = 1; i <= m; ++i)
        sum[i] += sum[i - 1];
    std::fill(sa, sa + n, -1);
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i + 1];
    for (int i : g)
        *--p[s[i]] = i;
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i];
    for (int i = 0; i != n; ++i)
        if (sa[i] > 0 && t[sa[i] - 1] == L)
            *p[s[sa[i] - 1]]++ = sa[i] - 1;
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i + 1];
    for (int i = n; i--;)
        if (sa[i] > 0 && t[sa[i] - 1] == S)
            *--p[s[sa[i] - 1]] = sa[i] - 1;
    int tmp[n], M = -1;
    for (int i = 0, lst = -1; i != n; ++i)
        if (lms(sa[i]))
            tmp[sa[i]] = ~lst && equal(lst, sa[i]) ? M : ++M, lst = sa[i];
    int h[g.size()];
    if (++M == int(g.size()))
        for (int i : g)
            h[tmp[i]] = i;
    else
    {
        int ns[g.size()];
        for (int i = 0; i != int(g.size()); ++i)
            ns[i] = tmp[g[i]];
        SAIS(ns, h, g.size(), M);
        for (int &i : h)
            i = g[i];
    }
    std::reverse(h, h + g.size());
    std::fill(sa, sa + n, -1);
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i + 1];
    for (int i : h)
        *--p[s[i]] = i;
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i];
    for (int i = 0; i != n; ++i)
        if (sa[i] > 0 && t[sa[i] - 1] == L)
            *p[s[sa[i] - 1]]++ = sa[i] - 1;
    for (int i = 0; i != m; ++i)
        p[i] = sa + sum[i + 1];
    for (int i = n; i--;)
        if (sa[i] > 0 && t[sa[i] - 1] == S)
            *--p[s[sa[i] - 1]] = sa[i] - 1;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::string sss;
    int s[1000005], sa[1000005];
    std::cin >> sss;
    std::copy(sss.begin(), sss.end(), s);
    s[sss.size()] = 0;
    SAIS(s, sa, sss.size() + 1, 128);
    for (std::size_t i = 1; i <= sss.size(); ++i)
        std::cout << sa[i] + 1 << " \n"[i == sss.size()];
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
int n, m, q, sa[1000005], rk[1000005], sum[1000005], height[1000005];
char s[1000005];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> (s + 1);
    n = std::strlen(s + 1);
    m = 128;
    for (int i = 1; i <= n; ++i)
        ++sum[rk[i] = s[i]];
    for (int i = 1; i <= m; ++i)
        sum[i] += sum[i - 1];
    for (int i = n; i; --i)
        sa[sum[rk[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        static int cnt, tmp[1 << 20 | 5];
        cnt = 0;
        for (int i = n - k + 1; i <= n; ++i)
            tmp[++cnt] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > k)
                tmp[++cnt] = sa[i] - k;
        std::fill(sum + 1, sum + 1 + m, 0);
        for (int i = 1; i <= n; ++i)
            ++sum[rk[i]];
        for (int i = 1; i <= m; ++i)
            sum[i] += sum[i - 1];
        for (int i = n; i; --i)
            sa[sum[rk[tmp[i]]]--] = tmp[i];
        std::copy(rk + 1, rk + 1 + n, tmp + 1);
        rk[sa[1]] = m = 1;
        for (int i = 2; i <= n; ++i)
            rk[sa[i]] = tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k] ? m : ++m;
        if (n == m)
            break;
    }
    for (int i = 1; i <= n; ++i)
        std::cout << sa[i] << " \n"[i == n];
    return 0;
}

// This Code was made by Chinese_zjc_.
int n, m;
template <class Type>
class LCT
{
private:
    class node
    {
    public:
        Type val, sum;
        int son[2], fa;
        bool rev;
        node() : val(), sum(), son(), fa() {}
        node(Type val_) : val(val_), sum(val_), son(), fa() {}
        void clear()
        {
            val = sum = Type();
            son[0] = son[1] = fa = 0;
        }
    } tree[100005];

public:
    LCT() {}
    void pushup(int now) { tree[now].sum = tree[now].val ^ tree[tree[now].son[0]].sum ^ tree[tree[now].son[1]].sum; }
    void pushdown(int now)
    {
        if (tree[now].rev)
        {
            std::swap(tree[now].son[0], tree[now].son[1]);
            tree[tree[now].son[0]].rev ^= true;
            tree[tree[now].son[1]].rev ^= true;
            tree[now].rev = false;
        }
    }
    void init_splay(int now)
    {
        if (~query_son(now))
            init_splay(tree[now].fa);
        pushdown(now);
    }
    int query_son(int now)
    {
        int fa = tree[now].fa, res = 2;
        while (res--)
            if (tree[fa].son[res] == now)
                break;
        return res;
    }
    void connect(int A, int B, int which)
    {
        if (A && ~which)
            tree[A].son[which] = B;
        if (B)
            tree[B].fa = A;
    }
    void rotate(int now)
    {
        int fa = tree[now].fa;
        bool nowg = query_son(now);
        connect(tree[fa].fa, now, query_son(fa));
        connect(fa, tree[now].son[!nowg], nowg);
        connect(now, fa, !nowg);
        pushup(fa);
    }
    void splay(int now)
    {
        init_splay(now);
        for (int fa = tree[now].fa; ~query_son(now); rotate(now), fa = tree[now].fa)
            if (query_son(fa) == query_son(now))
                rotate(fa);
    }
    void access(int now)
    {
        for (int lst = 0; now; lst = now, now = tree[now].fa)
        {
            splay(now);
            tree[now].son[1] = lst;
            pushup(now);
        }
    }
    void reverse(int now) { tree[now].rev ^= true; }
    void make_root(int now)
    {
        access(now);
        splay(now);
        reverse(now);
    }
    int find_root(int now)
    {
        access(now);
        splay(now);
        for (pushdown(now); tree[now].son[0]; pushdown(now))
            now = tree[now].son[0];
        splay(now);
        return now;
    }
    void split(int A, int B)
    {
        make_root(A);
        access(B);
        splay(B);
    }
    bool link(int A, int B)
    {
        make_root(A);
        int root = find_root(B);
        if (A == root)
            return false;
        make_root(B);
        tree[B].fa = A;
        access(B);
        return true;
    }
    bool cut(int A, int B)
    {
        split(A, B);
        if (tree[B].son[0] != A || tree[A].son[1])
            return false;
        tree[A].fa = tree[B].son[0] = 0;
        pushup(B);
        return true;
    }
    int sum(int A, int B)
    {
        split(A, B);
        pushup(B);
        return tree[B].sum;
    }
    void modify(int pos, int val)
    {
        splay(pos);
        tree[pos].val = val;
        pushup(pos);
    }
    void _visit(int now = 0)
    {
        if (!now)
        {
            for (int i = 1; i <= n; ++i)
                if (!~query_son(i))
                    _visit(i);
            return;
        }
        if (tree[now].son[0])
            _visit(tree[now].son[0]);
        if (tree[now].fa)
            std::cout << "   " << tree[now].fa << ' ' << now << ' ' << query_son(now) << std::endl;
        if (tree[now].son[1])
            _visit(tree[now].son[1]);
    }
};
LCT<int> lct;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        static int x;
        std::cin >> x;
        lct.modify(i, x);
    }
    for (int i = 1; i <= m; ++i)
    {
        static int opt, x, y;
        std::cin >> opt >> x >> y;
        switch (opt)
        {
        case 0:
            std::cout << lct.sum(x, y) << std::endl;
            break;
        case 1:
            lct.link(x, y);
            break;
        case 2:
            lct.cut(x, y);
            break;
        case 3:
            lct.modify(x, y);
            break;
        }
    }
    return 0;
}

// This Code was made by Chinese_zjc_.
namespace answer
{
    const unsigned MOD = 998244353;
    struct mint
    {
        unsigned v;
        mint(unsigned v_ = 0) : v(v_) {}
        mint operator-() const { return v ? MOD - v : *this; }
        mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
        mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
        mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
        mint &operator/=(const mint &X) { return *this *= X.inv(); }
        mint pow(long long B) const
        {
            B %= MOD - 1;
            if (B < 0)
                B += MOD - 1;
            mint res = 1, A = *this;
            while (B)
            {
                if (B & 1)
                    res *= A;
                B >>= 1;
                A *= A;
            }
            return res;
        }
        mint inv() const { return pow(MOD - 2); }
        friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
        friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
        friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
        friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
        friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
        friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
        friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
        explicit operator bool() const { return v; }
    } fact[200005], ifact[200005], inv[200005], d[200005], id[200005], x, y, xn, yn, h[100005];
    std::vector<mint> omega[19];
    mint Cn(int m) { return 0 <= m ? d[m] * ifact[m] : 0; }
    mint iCn(int m) { return 0 <= m ? id[m] * fact[m] : 0; }
    mint C(int n, int m) { return 0 <= m && m <= n ? fact[n] * ifact[m] * ifact[n - m] : 0; }
    mint iC(int n, int m) { return 0 <= m && m <= n ? ifact[n] * fact[m] * fact[n - m] : 0; }
    typedef std::vector<mint> poly;
    int n, ra, rb, m;
    void init()
    {
        fact[0] = 1;
        for (int i = 1; i <= 200000; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[200000] = fact[200000].inv();
        for (int i = 200000; i; --i)
            ifact[i - 1] = ifact[i] * i;
        for (int i = 1; i <= 200000; ++i)
            inv[i] = ifact[i] * fact[i - 1];
        d[0] = 1;
        for (int i = 0; i != 200000; ++i)
            d[i + 1] = d[i] * (n - i);
        for (int i = 0; i <= 200000; ++i)
            id[i] = d[i].inv();
        xn = x.pow(n);
        yn = y.pow(n);
        for (int i = 0; i <= 18; ++i)
        {
            mint w = mint(3).pow((MOD - 1) >> i >> 1);
            omega[i].resize(1 << i);
            omega[i][0] = 1;
            for (int j = 1; j != 1 << i; ++j)
                omega[i][j] = omega[i][j - 1] * w;
        }
    }
    void NTT(poly &X)
    {
        static std::vector<std::size_t> rev;
        if (rev.size() != X.size())
        {
            rev.resize(X.size());
            for (std::size_t i = 0; i != rev.size(); ++i)
                rev[i] = (rev[i >> 1] | (i & 1 ? rev.size() : 0)) >> 1;
        }
        for (std::size_t i = 0; i != X.size(); ++i)
            if (i < rev[i])
                std::swap(X[i], X[rev[i]]);
        unsigned long long v[X.size()];
        for (std::size_t i = 0; i != X.size(); ++i)
            v[i] = X[i].v;
        for (std::size_t i = 1, l = 0; i != X.size(); i <<= 1, ++l)
        {
            for (std::size_t j = 0; j != X.size(); j += i << 1)
            {
                for (std::size_t k = 0; k != i; ++k)
                {
                    unsigned long long A = v[j + k], B = v[i + j + k] * omega[l][k].v % MOD;
                    v[j + k] = A + B;
                    v[i + j + k] = A + MOD - B;
                }
            }
            if (i == 262144)
                for (std::size_t i = 0; i != X.size(); ++i)
                    v[i] %= MOD;
        }
        for (std::size_t i = 0; i != X.size(); ++i)
            X[i] = v[i] % MOD;
    }
    void INTT(poly &X)
    {
        NTT(X);
        std::reverse(X.begin() + 1, X.end());
        mint inv = mint(X.size()).inv();
        for (auto &i : X)
            i *= inv;
    }
    std::size_t up(std::size_t len) { return len == 1 ? 1 : 1 << (32 - __builtin_clz(len - 1)); }
    poly operator*(const poly &A, const poly &B)
    {
        std::size_t len = up(A.size() + B.size() - 1);
        poly a(A), b(B);
        a.resize(len);
        b.resize(len);
        NTT(a);
        NTT(b);
        for (std::size_t i = 0; i != len; ++i)
            a[i] *= b[i];
        INTT(a);
        a.resize(A.size() + B.size() - 1);
        return a;
    }
    poly operator*(const mint &A, const poly &B)
    {
        poly res = B;
        for (auto &i : res)
            i *= A;
        return res;
    }
    poly operator+(const poly &A, const poly &B)
    {
        poly res(std::max(A.size(), B.size()));
        for (std::size_t i = 0; i != A.size(); ++i)
            res[i] += A[i];
        for (std::size_t i = 0; i != B.size(); ++i)
            res[i] += B[i];
        return res;
    }
    poly operator-(const poly &A, const poly &B)
    {
        poly res(std::max(A.size(), B.size()));
        for (std::size_t i = 0; i != A.size(); ++i)
            res[i] += A[i];
        for (std::size_t i = 0; i != B.size(); ++i)
            res[i] -= B[i];
        return res;
    }
    poly INV(const poly &X)
    {
        assert(X.front());
        poly res(1, X.front().inv());
        for (std::size_t i = 1; i < X.size(); res.resize(i <<= 1))
        {
            poly tmp(X.begin(), X.begin() + std::min(X.size(), i << 1));
            tmp.resize(i << 2);
            res.resize(i << 2);
            NTT(tmp);
            NTT(res);
            for (std::size_t j = 0; j != i << 2; ++j)
                res[j] = (2 - res[j] * tmp[j]) * res[j];
            INTT(res);
        }
        res.resize(X.size());
        return res;
    }
    poly QIUDAO(const poly &X)
    {
        poly res = X;
        for (std::size_t i = 0; i != res.size(); ++i)
            res[i] *= i;
        return res;
    }
    poly JIFEN(const poly &X)
    {
        poly res = X;
        for (std::size_t i = 0; i != res.size(); ++i)
            res[i] *= inv[i];
        return res;
    }
    poly LN(const poly &X)
    {
        assert(X.front() == 1);
        poly res = QIUDAO(X) * INV(X);
        res.resize(X.size());
        return JIFEN(res);
    }
    poly resize(poly X, const std::size_t size) { return X.resize(size), X; }
    poly EXP(const poly &X)
    {
        assert(X.front() == 0);
        poly res(1, 1);
        for (std::size_t i = 1; i < X.size(); res.resize(i <<= 1))
            res = res * (poly{1} - LN(resize(res, std::min(X.size(), i << 1))) +
                         poly(X.begin(), X.begin() + std::min(X.size(), i << 1)));
        res.resize(X.size());
        return res;
    }
    poly v0, v, tmp, ans, H;
    poly solve1(int l, int r)
    {
        if (r - l == 1)
            return {h[l]};
        int mid = (l + r) >> 1;
        poly L(mid - l + 1), R(r - mid + 1);
        for (int i = 0; i <= mid - l; ++i)
            L[i] = ((mid - l - i) & 1 ? MOD - 1 : 1) * C(mid - l, i);
        for (int i = 0; i <= r - mid; ++i)
            R[i] = C(r - mid, i);
        L = L * solve1(mid, r);
        R = R * solve1(l, mid);
        return L + R;
    }
    std::pair<poly, poly> solve2(const poly &X, int l, int r)
    {
        if (r - l == 1)
            return {{X[l]}, {1, MOD - 2 * l}};
        int mid = (l + r) >> 1;
        std::pair<poly, poly> L = solve2(X, l, mid), R = solve2(X, mid, r);
        return {L.first * R.second + L.second * R.first, L.second * R.second};
    }
    poly Ln(poly G)
    {
        poly F;
        F.push_back(0);
        for (std::size_t i = 1; i != G.size(); ++i)
        {
            mint tmp = i * G[i];
            for (std::size_t j = 1; j != i; ++j)
                tmp -= (i - j) * F[i - j] * G[j];
            F.push_back(tmp / i);
        }
        return F;
    }
    poly Exp(poly F)
    {
        poly G;
        G.push_back(1);
        for (std::size_t i = 1; i != F.size(); ++i)
        {
            mint tmp = 0;
            for (std::size_t j = 0; j != i; ++j)
                tmp += (i - j) * F[i - j] * G[j];
            G.push_back(tmp / i);
        }
        return G;
    }
    signed main()
    {
        std::ios::sync_with_stdio(false);
        std::cin >> n;
        v.resize(n);
        init();
        for (int i = 0; i != n; ++i)
            std::cin >> v[i];
        v = EXP(v);
        for (int i = 0; i != n; ++i)
            std::cout << v[i] << " \n"[i + 1 == n];
        return 0;
    }
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
struct gg
{
    gg()
    {
        freopen("tree.in", "r", stdin) && freopen("tree.out", "w", stdout);
        std::ios::sync_with_stdio(false);
    }
} goodhabits;
int read()
{
    static int x;
    std::cin >> x;
    return x;
}
const int MOD = 998244353;
struct mint
{
    unsigned v;
    mint(unsigned v_ = 0) : v(v_) {}
    mint operator-() const { return v ? mint(MOD - v) : mint(); }
    mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator*=(const mint &X) { return v = 1ll * v * X.v % MOD, *this; }
    mint &operator/=(const mint &X) { return *this *= X.inv(); }
    mint pow(unsigned b) const
    {
        mint res(1), a = *this;
        while (b)
        {
            if (b & 1)
                res *= a;
            a *= a;
            b >>= 1;
        }
        return res;
    }
    mint inv() const { return pow(MOD - 2); }
    friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
    friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
    friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
    friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
    friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
    friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
    friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
    friend bool operator!=(const mint &A, const mint &B) { return A.v != B.v; }
    explicit operator bool() const { return v; }
};
typedef std::vector<mint> poly;
typedef std::valarray<mint> vector;
std::ostream &operator<<(std::ostream &A, const poly &B)
{
    for (auto i : B)
        A << std::setw(10) << i;
    return A;
}
std::ostream &operator<<(std::ostream &A, const vector &B)
{
    for (auto i : B)
        A << std::setw(10) << i;
    return A;
}
poly &operator*=(poly &A, const mint &B)
{
    for (auto &i : A)
        i *= B;
    return A;
}
mint res(poly A, poly B)
{
    mint r = 1;
    int n = A.size() - 1, m = B.size() - 1;
    r *= B.back().pow(n);
    B *= B.back().inv();
    while (B.size() > 1)
    {
        for (int i = n - m; i >= 0; --i)
        {
            mint g = A[i + m];
            for (int j = 0; j <= m; ++j)
                A[i + j] -= B[j] * g;
        }
        while (n && A[n] == 0)
            --n;
        if (A[n] == 0)
            return 0;
        A.resize(n + 1);
        std::swap(A, B);
        std::swap(n, m);
        if (n * m % 2)
            r *= MOD - 1;
        r *= B.back().pow(n);
        B *= B.back().inv();
    }
    return r;
}
struct matrix
{
    int d;
    std::valarray<vector> v;
    explicit matrix(int d_) : d(d_), v(vector(d), d) {}
    vector &operator[](const int &x) { return v[x]; }
    const vector &operator[](const int &x) const { return v[x]; }
    matrix &operator+=(const matrix &X) { return v += X.v, *this; }
    matrix &operator-=(const matrix &X) { return v -= X.v, *this; }
    matrix &operator*=(const matrix &X) { return *this = *this * X; }
    matrix &operator*=(const mint &X)
    {
        for (auto &i : v)
            i *= X;
        return *this;
    }
    matrix operator-() const
    {
        matrix ret = *this;
        for (auto &i : ret.v)
            i = -i;
        return ret;
    }
    friend matrix operator*(const matrix &A, const matrix &B)
    {
        int d = A.d;
        matrix res(d);
        for (int i = 0; i != d; ++i)
            for (int j = 0; j != d; ++j)
                for (int k = 0; k != d; ++k)
                    res[i][k] += A[i][j] * B[j][k];
        return res;
    }
    void Gauss()
    {
        for (int i = 0; i != d; ++i)
        {
            if (!v[i][i])
                for (int j = i; ++j != d;)
                    if (v[j][i])
                    {
                        v[i] += v[j];
                        break;
                    }
            mint g = v[i][i].inv();
            for (int j = i; ++j != d;)
                v[j] -= v[j][i] * g * v[i];
        }
    }
    mint Del() const
    {
        matrix tmp = *this;
        mint res = 1;
        tmp.Gauss();
        for (int i = 0; i != d; ++i)
            res *= tmp[i][i];
        return res;
    }
    mint DelHessenberg() const
    {
        mint f[d + 1];
        f[0] = 1;
        for (int i = 0; i != d; ++i)
        {
            mint t = 1;
            for (int j = 0; ++j; t *= -v[i + j][i + j - 1])
            {
                f[i + j] += f[i] * t * v[i][i + j - 1];
                if (i + j == d)
                    break;
            }
        }
        return f[d];
    }
    void Hessenberg()
    {
        for (int i = 0; i != d - 1; ++i)
        {
            if (!v[i + 1][i])
                for (int j = i + 1; ++j != d;)
                    if (v[j][i])
                    {
                        v[i + 1] += v[j];
                        for (int k = 0; k != d; ++k)
                            v[k][i + 1] -= v[k][j];
                        break;
                    }
            for (int j = d; --j != i + 1;)
            {
                mint tmp = v[j][i] / v[j - 1][i];
                v[j] -= tmp * v[j - 1];
                for (int k = 0; k != d; ++k)
                    v[k][j - 1] += tmp * v[k][j];
            }
        }
    }
    void solveEquation(vector &c)
    {
        for (int i = 0; i != d; ++i)
        {
            if (!v[i][i])
                for (int j = i; ++j != d;)
                    if (v[j][i])
                    {
                        v[i] += v[j];
                        break;
                    }
            mint g = v[i][i].inv();
            for (int j = i; ++j != d;)
                c[j] -= v[j][i] * g * c[i], v[j] -= v[j][i] * g * v[i];
        }
        for (int i = d; i--;)
        {
            for (int j = i; ++j != d;)
                c[i] -= v[i][j] * c[j];
            c[i] /= v[i][i];
        }
    }
};
struct work
{
    int n;
    matrix G;
    vector x;
    poly charp;
    work() : n(read()), G(n), x(n), charp() {}
    void solve()
    {
        for (int i = 0; i != n; ++i)
            for (int j = 0; j != n; ++j)
            {
                static mint tmp;
                std::cin >> tmp;
                G[i][j] -= tmp;
                G[j][j] += tmp;
            }
        matrix tmp = G;
        tmp.Gauss();
        for (int i = n; i--;)
        {
            mint y = 0;
            for (int j = i; ++j != n;)
                y -= x[j] * tmp[i][j];
            x[i] = tmp[i][i] ? y / tmp[i][i] : 1;
        }
        tmp = G;
        for (int i = 0; i != n; ++i)
            if (x[i])
            {
                tmp[i].resize(n);
                tmp[i][i] = 1;
                x *= tmp.Del() / x[i];
                break;
            }
        tmp = -G;
        tmp.Hessenberg();
        vector R(n);
        matrix L(n);
        for (int i = 0; i != n; ++i)
        {
            L[i][0] = 1;
            for (int j = 1; j != n; ++j)
                L[i][j] = L[i][j - 1] * i;
            R[i] = tmp.DelHessenberg() - mint(i).pow(n);
            for (int j = 0; j != n; ++j)
                tmp[j][j] += 1;
        }
        L.solveEquation(R);
        charp.assign(std::begin(R), std::end(R));
        charp.push_back(1);
    }
} A, B;
signed main()
{
    A.solve();
    B.solve();
    poly p(++A.charp.begin(), A.charp.end()), q(++B.charp.begin(), B.charp.end());
    for (std::size_t i = 1; i < q.size(); i += 2)
        q[i] *= MOD - 1;
    mint g = res(p, q);
    for (int i = 0; i != A.n; ++i)
        for (int j = 0; j != B.n; ++j)
            std::cout << A.x[i] * B.x[j] * g << " \n"[j + 1 == B.n];
    return 0;
}

using poly = std::vector<mint>;
poly BM(const poly &x)
{
    poly cur(1), lst(1);
    cur[0] = lst[0] = 1;
    int lp = 0;
    mint lt = 0;
    for (int i = 0; i < (int)x.size(); ++i)
    {
        mint t = 0;
        for (int j = 0; j < (int)cur.size(); ++j)
        {
            t += x[i - j] * cur[j];
        }
        if (t == 0)
            continue;
        if ((int)cur.size() == 1)
        {
            cur.resize(i + 2);
            lp = i, lt = t;
            continue;
        }
        mint tmp = -t / lt;
        poly c(i - lp);
        for (mint v : lst)
            c.push_back(tmp * v);
        if (c.size() < cur.size())
            c.resize(cur.size());
        else
            lst = cur, lp = i, lt = t;
        for (int j = 0; j < (int)cur.size(); ++j)
            c[j] += cur[j];
        cur = c;
    }
    std::reverse(G.begin(), G.end());
    return cur;
}
poly mul(const poly &A, const poly &B, const poly &C)
{
    poly res(A.size() + B.size() - 1);
    for (std::size_t i = 0; i != A.size(); ++i)
        for (std::size_t j = 0; j != B.size(); ++j)
            res[i + j] += A[i] * B[j];
    while (res.size() >= C.size())
    {
        mint v = res.back() / C.back();
        for (std::size_t i = 1; i <= C.size(); ++i)
            res.end()[-i] -= v * C.end()[-i];
        res.pop_back();
    }
    return res;
}
poly power(poly A, long long B, poly C)
{
    poly res = {1};
    while (B)
    {
        if (B & 1)
            res = mul(res, A, C);
        A = mul(A, A, C);
        B >>= 1;
    }
    return res;
}

#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rep(i, a, b) for (int i = (a), I = (b); i <= I; ++i)
#define per(i, a, b) for (int i = (a), I = (b); i >= I; --i)
using i64 = long long;
using pii = pair<int, int>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

const int N = 1000005, inf = 1e9;
int n, m, a[N], fa[N], dep[N], siz[N], son[N], top[N];
vector<int> e[N];
int dp[N][2], f[N][2];

void dfs1(int u) {
    siz[u] = 1;
    dp[u][1] = a[u];
    for (auto v : e[u]) {
        e[v].erase(find(e[v].begin(), e[v].end(), u));
        fa[v] =  u, dep[v] = dep[u] + 1;
        dfs1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
    f[u][0] = dp[u][0], f[u][1] = dp[u][1];
    if (son[u]) {
        f[u][0] -= max(dp[son[u]][0], dp[son[u]][1]);
        f[u][1] -= dp[son[u]][0];
    }
}

using mat = array<array<int, 2>, 2>;
mat operator*(const mat &lhs, const mat &rhs) {
    mat res;
    rep(i, 0, 1) rep(j, 0, 1) res[i][j] = max(lhs[i][0] + rhs[0][j], lhs[i][1] + rhs[1][j]);
    return res;
}
mat get_mat(int u) {
    return {f[u][0], f[u][1], f[u][0], -inf};
}

const int M = N << 1;
int rt[N], ls[M], rs[M], md[M], par[M], tot;
pii tmp[N];
mat val[M];

void push_up(int p) {
    val[p] = val[rs[p]] * val[ls[p]];
}
int build(int l, int r) { 
    if (l == r) {
        int u = tmp[l].first;
        val[u] = get_mat(u);
        return u;
    }   
    int p = ++tot;
    int mid = l, sum = 0, cur = tmp[l].second;
    rep(i, l, r) sum += tmp[i].second;
    while (mid + 1 < r && (cur + tmp[mid + 1].second) * 2 <= sum) cur += tmp[++mid].second;
    md[p] = mid;
    ls[p] = build(l, mid);
    rs[p] = build(mid + 1, r);
    par[ls[p]] = par[rs[p]] = p;
    push_up(p);
    return p;
}
void dfs2(int u) {
    for (int x = u; x; x = son[x]) for (auto y : e[x]) if (y != son[x]) dfs2(y);
    int cnt = 0;
    for (int x = u; x; x = son[x]) tmp[++cnt] = {x, siz[x] - siz[son[x]]}, top[x] = u;
    rt[u] = build(1, cnt);
}
void modify(int u) {
    val[u] = get_mat(u);
    for (u = par[u]; u; u = par[u]) push_up(u);
}

void query_sub(int u) {
    int r = rt[u];
    dp[u][0] = val[r][0][0], dp[u][1] = val[r][0][1];
}
void modify(int u, int x) {
    f[u][1] += x - a[u];
    a[u] = x;
    while (u) {
        int t = top[u], x = fa[t];
        f[x][0] -= max(dp[t][0], dp[t][1]);
        f[x][1] -= dp[t][0];
        modify(u);
        query_sub(t);
        f[x][0] += max(dp[t][0], dp[t][1]);
        f[x][1] += dp[t][0];
        u = x;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n - 1) {
        int u, v; 
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    dfs1(1), tot = n, dfs2(1);

    int last_ans = 0;
    while (m--) {
        int u, x; 
        cin >> u >> x;
        u ^= last_ans;
        modify(u, x);
        cout << (last_ans = max(dp[1][0], dp[1][1])) << "\n";
    }

    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
int n, m, s, t, head[5005], cur[5005], cnt;
long long flow, dis[5005];
struct edge
{
    int n, t;
    long long v;
} e[100005];
void add_edge(int A, int B, long long C)
{
    e[cnt].n = head[A];
    e[cnt].t = B;
    e[cnt].v = C;
    head[A] = cnt++;
}
void add_flow(int A, int B, long long C)
{
    add_edge(A, B, C);
    add_edge(B, A, 0);
}
bool get_dis()
{
    std::fill(dis, dis + n, -1);
    dis[s] = 0;
    std::queue<int> que;
    que.push(s);
    while (!que.empty())
    {
        int now = que.front();
        que.pop();
        for (int i = head[now]; ~i; i = e[i].n)
            if (e[i].v && !~dis[e[i].t])
            {
                dis[e[i].t] = dis[now] + 1;
                que.push(e[i].t);
            }
    }
    return ~dis[t];
}
long long dfs(int now = s, long long flow = LLONG_MAX)
{
    if (now == t || !flow)
        return flow;
    long long res = 0;
    for (int &i = cur[now]; ~i; i = e[i].n)
        if (e[i].v && dis[e[i].t] == dis[now] + 1)
        {
            int tmp = dfs(e[i].t, std::min(flow, e[i].v));
            e[i].v -= tmp;
            e[i ^ 1].v += tmp;
            res += tmp;
            flow -= tmp;
            if (!flow)
                break;
        }
    return res;
}
void Dinic()
{
    while (get_dis())
    {
        std::copy(head, head + n, cur);
        flow += dfs();
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::memset(head, -1, sizeof(head));
    std::cin >> n >> m >> s >> t;
    ++n;
    for (int i = 0, u, v, w; i != m; ++i)
    {
        std::cin >> u >> v >> w;
        add_flow(u, v, w);
    }
    Dinic();
    std::cout << flow << std::endl;
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
int n, m, s, t, head[5005], cur[5005], cnt, flow;
long long cost, dis[5005], h[5005];
bool in[5005];
struct edge
{
    int n, t, v, w;
} e[100005];
void add_edge(int A, int B, int C, int D)
{
    e[cnt].n = head[A];
    e[cnt].t = B;
    e[cnt].v = C;
    e[cnt].w = D;
    head[A] = cnt++;
}
void add_flow(int A, int B, int C, int D)
{
    add_edge(A, B, C, D);
    add_edge(B, A, 0, -D);
}
bool get_dis()
{
    for (int i = 0; i <= n; ++i)
        h[i] += dis[i];
    std::fill(dis, dis + n, LLONG_MAX);
    dis[s] = 0;
    static bool flag;
    if (!flag)
    {
        std::queue<int> que;
        que.push(s);
        in[s] = true;
        while (!que.empty())
        {
            int now = que.front();
            que.pop();
            in[now] = false;
            for (int i = head[now]; ~i; i = e[i].n)
            {
                if (e[i].v && dis[e[i].t] > dis[now] + e[i].w)
                {
                    dis[e[i].t] = dis[now] + e[i].w;
                    if (!in[e[i].t])
                        que.push(e[i].t);
                    in[e[i].t] = true;
                }
            }
        }
        flag = true;
    }
    else
    {
        std::priority_queue<std::pair<long long, int>> que;
        que.push({-dis[s], s});
        while (!que.empty())
        {
            int now = que.top().second;
            if (dis[now] + que.top().first)
            {
                que.pop();
                continue;
            }
            que.pop();
            for (int i = head[now]; ~i; i = e[i].n)
                if (e[i].v && dis[e[i].t] > dis[now] + e[i].w + h[now] - h[e[i].t])
                    que.push({-(dis[e[i].t] = dis[now] + e[i].w + h[now] - h[e[i].t]), e[i].t});
        }
    }
    return dis[t] != LLONG_MAX;
}
int dfs(int now = s, int flow = INT_MAX)
{
    if (now == t || !flow)
        return flow;
    in[now] = true;
    int res = 0;
    for (int &i = cur[now]; ~i; i = e[i].n)
        if (e[i].v && !in[e[i].t] && dis[e[i].t] + h[e[i].t] == dis[now] + h[now] + e[i].w)
        {
            int tmp = dfs(e[i].t, std::min(flow, e[i].v));
            cost += 1ll * e[i].w * tmp;
            e[i].v -= tmp;
            e[i ^ 1].v += tmp;
            res += tmp;
            flow -= tmp;
            if (!flow)
                break;
        }
    in[now] = false;
    return res;
}
void Dinic()
{
    while (get_dis())
    {
        std::copy(head, head + n, cur);
        flow += dfs();
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::memset(head, -1, sizeof(head));
    std::cin >> n >> m >> s >> t;
    ++n;
    for (int i = 0, u, v, w, c; i != m; ++i)
    {
        std::cin >> u >> v >> w >> c;
        add_flow(u, v, w, c);
    }
    Dinic();
    std::cout << flow << ' ' << cost << std::endl;
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
std::vector<int> to[505];
int n, m, k, match[505], ans, vis[505];
bool dfs(const int &now, const int &tag)
{
    if (vis[now] == tag)
        return false;
    vis[now] = tag;
    for (auto i : to[now])
        if (!match[i] || dfs(match[i], tag))
        {
            match[i] = now;
            return true;
        }
    return false;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m >> k;
    for (int i = 1, u, v; i <= k; ++i)
    {
        std::cin >> u >> v;
        to[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i)
        if (dfs(i, i))
            ++ans;
    std::cout << ans << std::endl;
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
int n, m, lst[505], matchl[505], matchr[505];
long long v[505][505], lm[505], rm[505], d[505];
bool visl[505], visr[505];
void Match(int now)
{
    static int tmp;
    while (now)
    {
        tmp = matchl[lst[now]];
        matchl[lst[now]] = now;
        matchr[now] = lst[now];
        now = tmp;
    }
}
void bfs(int s)
{
    std::fill(visl + 1, visl + 1 + n, false);
    std::fill(visr + 1, visr + 1 + n, false);
    std::fill(d + 1, d + 1 + n, LLONG_MAX / 4);
    std::queue<int> que;
    que.push(s);
    while (true)
    {
        while (!que.empty())
        {
            int now = que.front();
            que.pop();
            visl[now] = true;
            for (int i = 1; i <= n; ++i)
                if (!visr[i] && lm[now] + rm[i] - v[now][i] < d[i])
                {
                    d[i] = lm[now] + rm[i] - v[now][i];
                    lst[i] = now;
                    if (!d[i])
                    {
                        visr[i] = true;
                        if (!matchr[i])
                            return Match(i);
                        else
                            que.push(matchr[i]);
                    }
                }
        }
        long long down = LLONG_MAX / 4;
        for (int i = 1; i <= n; ++i)
            if (!visr[i])
                down = std::min(down, d[i]);
        for (int i = 1; i <= n; ++i)
        {
            if (visl[i])
                lm[i] -= down;
            if (visr[i])
                rm[i] += down;
            else
                d[i] -= down;
        }
        for (int i = 1; i <= n; ++i)
            if (!visr[i] && !d[i])
            {
                visr[i] = true;
                if (!matchr[i])
                    return Match(i);
                else
                    que.push(matchr[i]);
            }
    }
}
long long KM()
{
    for (int i = 1; i <= n; ++i)
        lm[i] = *std::max_element(v[i] + 1, v[i] + 1 + n);
    for (int i = 1; i <= n; ++i)
        bfs(i);
    long long res = 0;
    for (int i = 1; i <= n; ++i)
        res += lm[i] + rm[i];
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            v[i][j] = LLONG_MIN / 4;
    for (int i = 1; i <= m; ++i)
    {
        static int a, b;
        static long long c;
        std::cin >> a >> b >> c;
        v[a][b] = std::max(v[a][b], c);
    }
    std::cout << KM() << std::endl;
    for (int i = 1; i <= n; ++i)
        std::cout << matchr[i] << " \n"[i == n];
    return 0;
}

class node
{
public:
    int v, p;
    friend bool operator<(const node &A, const node &B)
    {
        return A.v == B.v ? A.p < B.p : A.v < B.v;
    }
};
template <class Type>
class heap
{
private:
    class node
    {
    private:
        int dis;
        void swap_son() { swap(lson, rson); }
        bool bad() const { return lson_dis() < rson_dis(); }
        int lson_dis() const { return lson ? lson->dis : -1; }
        int rson_dis() const { return rson ? rson->dis : -1; }

    public:
        node(Type VAL = Type(), node *LSON = 0, node *RSON = 0) : dis(0), val(VAL), lson(LSON), rson(RSON) {}
        Type val;
        node *lson, *rson;
        void update()
        {
            if (bad())
                swap_son();
            dis = rson_dis() + 1;
        }
        friend node *merge_node(node *A, node *B)
        {
            if (A == nullptr)
                return B;
            if (B == nullptr)
                return A;
            if (B->val < A->val)
                swap(A, B);
            A->rson = merge_node(A->rson, B);
            A->update();
            return A;
        }
    };
    node *root;

public:
    bool empty() const { return root == 0; }
    Type top() const { return empty() ? Type() : root->val; }
    void push(const Type &x)
    {
        if (empty())
            root = new node(x);
        else
            merge_node(root, new node(x));
    }
    void pop()
    {
        if (empty())
            return;
        node *tmp = root;
        root->update();
        if (root->rson)
            root = merge_node(root->lson, root->rson);
        else if (root->lson)
            root = root->lson;
        else
            root = 0;
        delete tmp;
    }
    void merge(heap &x)
    {
        if (x.empty() || &x == this)
            return;
        if (empty())
        {
            root = x.root;
            return;
        }
        root = merge_node(root, x.root);
        x.root = 0;
    }
};

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
unsigned long long seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 Rand(seed);
struct treap
{
    struct node
    {
        node *lson, *rson;
        int siz, v, w;
        node(int x) : lson(), rson(), siz(1), v(x), w(Rand()) {}
        void pushup() { siz = (lson ? lson->siz : 0) + 1 + (rson ? rson->siz : 0); }
    } * root;
    void insert(int x)
    {
        if (root == nullptr)
            return void(root = new node(x));
        std::pair<node *, node *> tmp = split(root, x);
        root = merge(merge(tmp.first, new node(x)), tmp.second);
    }
    void erase(int x)
    {
        std::pair<node *, node *> tmp = split(root, x), g = split(tmp.second, x + 1);
        root = merge(tmp.first, merge(merge(g.first->lson, g.first->rson), g.second));
        delete g.first;
    }
    int rk(int x) const { return rk_(root, x); }
    int rt(int x) const { return rt_(root, x); }
    int rk_(node *now, int x) const
    {
        if (now == nullptr)
            return 0;
        if (now->v < x)
            return (now->lson ? now->lson->siz : 0) + 1 + rk_(now->rson, x);
        else
            return rk_(now->lson, x);
    }
    int rt_(node *now, int x) const
    {
        if (now->lson)
        {
            if (x < now->lson->siz)
                return rt_(now->lson, x);
            x -= now->lson->siz;
        }
        if (x == 0)
            return now->v;
        --x;
        return rt_(now->rson, x);
    }
    std::pair<node *, node *> split(node *now, int x)
    {
        if (now == nullptr)
            return {};
        std::pair<node *, node *> tmp;
        if (now->v < x)
        {
            tmp = split(now->rson, x);
            now->rson = tmp.first;
            tmp.first = now;
        }
        else
        {
            tmp = split(now->lson, x);
            now->lson = tmp.second;
            tmp.second = now;
        }
        now->pushup();
        return tmp;
    }
    node *merge(node *A, node *B)
    {
        if (A == nullptr)
            return B;
        if (B == nullptr)
            return A;
        if (A->w < B->w)
        {
            A->rson = merge(A->rson, B);
            A->pushup();
            return A;
        }
        else
        {
            B->lson = merge(A, B->lson);
            B->pushup();
            return B;
        }
    }
} t;
int n, m;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    for (int i = 1, x; i <= n; ++i)
    {
        std::cin >> x;
        t.insert(x);
    }
    int ans = 0;
    for (int i = 1, lst = 0, opt, x; i <= m; ++i)
    {
        std::cin >> opt >> x;
        x ^= lst;
        switch (opt)
        {
        case 1:
            t.insert(x);
            break;
        case 2:
            t.erase(x);
            break;
        case 3:
            ans ^= (lst = t.rk(x) + 1);
            break;
        case 4:
            ans ^= (lst = t.rt(x - 1));
            break;
        case 5:
            ans ^= (lst = t.rt(t.rk(x) - 1));
            break;
        case 6:
            ans ^= (lst = t.rt(t.rk(x + 1)));
            break;
        }
        // if (opt > 2)
        //     std::cout << lst << '\n';
    }
    std::cout << ans << std::endl;
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
unsigned long long seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937_64 Rand(seed);
struct node
{
    node *lson, *rson;
    int val;
    unsigned size : 19, w : 13;
    node(int v = 0) : lson(), rson(), val(v), size(1), w(Rand()) {}
    void pushup() { size = (lson ? lson->size : 0) + 1 + (rson ? rson->size : 0); }
};
class treap
{
    node *root;
    static unsigned get(node *now) { return now ? now->size : 0; }
    static node *merge(node *A, node *B)
    {
        if (!A)
            return B;
        if (!B)
            return A;
        if (A->w < B->w)
        {
            node *res = new node(*A);
            res->rson = merge(A->rson, B);
            res->pushup();
            return res;
        }
        else
        {
            node *res = new node(*B);
            res->lson = merge(A, B->lson);
            res->pushup();
            return res;
        }
    }
    static std::pair<node *, node *> split(node *X, int val)
    {
        if (!X)
            return {};
        if (X->val < val)
        {
            node *res = new node(*X);
            std::pair<node *, node *> tmp = split(X->rson, val);
            res->rson = tmp.first;
            tmp.first = res;
            res->pushup();
            return tmp;
        }
        else
        {
            node *res = new node(*X);
            std::pair<node *, node *> tmp = split(X->lson, val);
            res->lson = tmp.second;
            tmp.second = res;
            res->pushup();
            return tmp;
        }
    }
    static unsigned rk_(node *now, int val)
    {
        if (!now)
            return 0;
        if (val <= now->val)
            return rk_(now->lson, val);
        else
            return get(now->lson) + 1 + rk_(now->rson, val);
    }
    static int find_(node *now, unsigned val)
    {
        if (val < get(now->lson))
            return find_(now->lson, val);
        val -= get(now->lson);
        if (val == 0)
            return now->val;
        --val;
        return find_(now->rson, val);
    }

public:
    treap(node *root = nullptr) : root(root) {}
    treap insert(int val) const
    {
        std::pair<node *, node *> tmp = split(root, val);
        return merge(tmp.first, merge(new node(val), tmp.second));
    }
    treap erase(int val) const
    {
        std::pair<node *, node *> A = split(root, val);
        std::pair<node *, node *> B = split(A.second, val + 1);
        if (B.first)
            return merge(merge(A.first, B.first->lson), merge(B.first->rson, B.second));
        else
            return merge(A.first, B.second);
    }
    unsigned rk(int val) const { return rk_(root, val); }
    int find(unsigned val) const { return find_(root, val); }
    void print(node *now) const
    {
        if (!root)
            return;
        if (!now)
            now = root, std::cout << 0 << ' ' << now << ',' << now->val << std::endl;
        if (now->lson)
            std::cout << now << ',' << now->val << ' ' << now->lson << ',' << now->lson->val << ' ' << 0 << std::endl,
                print(now->lson);
        if (now->rson)
            std::cout << now << ',' << now->val << ' ' << now->rson << ',' << now->rson->val << ' ' << 1 << std::endl,
                print(now->rson);
    }
} t[500005];
int n;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    t[0] = t[0].insert(-INT_MAX);
    t[0] = t[0].insert(+INT_MAX);
    std::cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        static int v, opt, x;
        std::cin >> v >> opt >> x;
        t[i] = t[v];
        switch (opt)
        {
        case 1:
            t[i] = t[i].insert(x);
            break;
        case 2:
            t[i] = t[i].erase(x);
            break;
        case 3:
            std::cout << t[i].rk(x) << '\n';
            break;
        case 4:
            std::cout << t[i].find(x) << '\n';
            break;
        case 5:
            std::cout << t[i].find(t[i].rk(x) - 1) << '\n';
            break;
        case 6:
            std::cout << t[i].find(t[i].rk(x + 1)) << '\n';
            break;
        }
    }
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 Rand(seed);
int n, m;
class treap
{
    struct node
    {
        node *lson, *rson;
        int v;
        unsigned w;
        std::size_t size;
        bool rev;
        node(int v_) : lson(), rson(), v(v_), w(Rand()), size(1), rev(false) {}
#define size(x) ((x) ? (x)->size : 0)
        void pushup()
        {
            size = 1 + size(lson) + size(rson);
        }
        void pushdown()
        {
            if (rev)
            {
                std::swap(lson, rson);
                if (lson)
                    lson->rev ^= true;
                if (rson)
                    rson->rev ^= true;
                rev = false;
            }
        }
    };
    node *root;
    node *merge(node *A, node *B)
    {
        if (!A)
            return B;
        if (!B)
            return A;
        if (A->w < B->w)
        {
            A->pushdown();
            A->rson = merge(A->rson, B);
            A->pushup();
            return A;
        }
        else
        {
            B->pushdown();
            B->lson = merge(A, B->lson);
            B->pushup();
            return B;
        }
    }
    std::pair<node *, node *> split(node *X, std::size_t size)
    {
        std::pair<node *, node *> res;
        if (!X)
            return res;
        X->pushdown();
        if (size(X->lson) < size)
        {
            std::pair<node *, node *> tmp = split(X->rson, size - size(X->lson) - 1);
            X->rson = tmp.first;
            res.first = X;
            res.second = tmp.second;
        }
        else
        {
            std::pair<node *, node *> tmp = split(X->lson, size);
            X->lson = tmp.second;
            res.first = tmp.first;
            res.second = X;
        }
        X->pushup();
        return res;
    }
    void visit_(node *now)
    {
        if (!now)
            return;
        now->pushdown();
        visit_(now->lson);
        std::cout << now->v << ' ';
        visit_(now->rson);
    }

public:
    void push_back(int v) { root = merge(root, new node(v)); }
    void reverse(std::size_t l, std::size_t r)
    {
        std::pair<node *, node *> tmp = split(root, l);
        node *L = tmp.first;
        tmp = split(tmp.second, r - l);
        tmp.first->rev ^= true;
        root = merge(L, merge(tmp.first, tmp.second));
    }
    void visit()
    {
        visit_(root);
    }
} a;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        a.push_back(i);
    for (int i = 1, x, y; i <= m; ++i)
    {
        std::cin >> x >> y;
        a.reverse(--x, y);
    }
    a.visit();
    std::cout << std::endl;
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 Rand(seed);
struct __attribute__((packed)) node
{
    node *lson, *rson;
    int v : 21;
    long long sum : 39;
    unsigned w : 16, size : 18;
    bool rev : 1;
    node(int v_) : lson(), rson(), v(v_), sum(v_), w(Rand()), size(1), rev() {}
#define size(x) ((x) ? (x)->size : 0)
    void pushup()
    {
        size = 1 + size(lson) + size(rson);
        sum = v + (lson ? lson->sum : 0) + (rson ? rson->sum : 0);
    }
    void pushdown()
    {
        if (rev)
        {
            node *tmp = lson;
            lson = rson;
            rson = tmp;
            if (lson)
                (lson = new node(*lson))->rev ^= true;
            if (rson)
                (rson = new node(*rson))->rev ^= true;
            rev = false;
        }
    }
};
class treap
{
private:
    node *root;
    node *merge(node *A, node *B) const
    {
        if (!A)
            return B;
        if (!B)
            return A;
        node *res;
        if (A->w < B->w)
        {
            res = new node(*A);
            res->pushdown();
            res->rson = merge(res->rson, B);
            res->pushup();
        }
        else
        {
            res = new node(*B);
            res->pushdown();
            res->lson = merge(A, res->lson);
            res->pushup();
        }
        return res;
    }
    std::pair<node *, node *> split(node *X, unsigned cnt)
    {
        std::pair<node *, node *> res;
        if (!X)
            return res;
        X = new node(*X);
        X->pushdown();
        if (size(X->lson) < cnt)
        {
            res.first = X;
            std::pair<node *, node *> tmp = split(X->rson, cnt - 1 - size(X->lson));
            res.second = tmp.second;
            X->rson = tmp.first;
        }
        else
        {
            res.second = X;
            std::pair<node *, node *> tmp = split(X->lson, cnt);
            res.first = tmp.first;
            X->lson = tmp.second;
        }
        X->pushup();
        return res;
    }
    long long sum(node *now, unsigned cnt)
    {
        if (!now || !cnt)
            return 0;
        if (size(now) <= cnt)
            return now->sum;
        long long res = 0;
        now->pushdown();
        if (now->lson)
        {
            if (now->lson->size <= cnt)
                res += now->lson->sum, cnt -= now->lson->size;
            else
                return sum(now->lson, cnt);
        }
        if (cnt)
            return res + now->v + sum(now->rson, cnt - 1);
        return res;
    }

public:
    explicit treap(node *root_) : root(root_) {}
    treap insert(unsigned pos, int v)
    {
        std::pair<node *, node *> tmp = split(root, pos);
        return treap(merge(merge(tmp.first, new node(v)), tmp.second));
    }
    treap erase(unsigned pos)
    {
        std::pair<node *, node *> tmp = split(root, pos);
        return treap(merge(tmp.first, split(tmp.second, 1).second));
    }
    treap reverse(unsigned l, unsigned r)
    {
        std::pair<node *, node *> tmp = split(root, l);
        node *L = tmp.first;
        tmp = split(tmp.second, r - l);
        node *m = new node(*tmp.first);
        m->rev ^= true;
        return treap(merge(L, merge(m, tmp.second)));
    }
    long long query(unsigned l, unsigned r) { return sum(root, r) - sum(root, l); }
};
std::vector<treap> a;
int n;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    a.push_back(treap(nullptr));
    for (int i = 1, v, opt; i <= n; ++i)
    {
        static long long p, x, ans;
        std::cin >> v >> opt;
        switch (opt)
        {
        case 1:
            std::cin >> p >> x;
            p ^= ans;
            x ^= ans;
            a.push_back(a[v].insert(p, x));
            break;
        case 2:
            std::cin >> p;
            p ^= ans;
            a.push_back(a[v].erase(p - 1));
            break;
        case 3:
            std::cin >> p >> x;
            p ^= ans;
            x ^= ans;
            a.push_back(a[v].reverse(--p, x));
            break;
        case 4:
            std::cin >> p >> x;
            p ^= ans;
            x ^= ans;
            a.push_back(a[v]);
            std::cout << (ans = a[i].query(--p, x)) << std::endl;
            break;
        }
    }
    return 0;
}

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
const double eps = 1e-10;
const double PI = std::acos(-1);
template <class T>
auto sqr(T x) { return x * x; }
struct point
{
    double x, y;
    point() : x(), y() {}
    point(double x, double y) : x(x), y(y) {}
    point operator~() const { return point(-y, x); }
    point operator-() const { return point(-x, -y); }
    point &operator+=(const point &X) { return x += X.x, y += X.y, *this; }
    point &operator-=(const point &X) { return x -= X.x, y -= X.y, *this; }
    point &operator*=(const double &X) { return x *= X, y *= X, *this; }
    friend point operator+(const point &A, const point &B) { return point(A) += B; }
    friend point operator-(const point &A, const point &B) { return point(A) -= B; }
    friend point operator*(const point &A, const double &B) { return point(A) *= B; }
    friend point operator*(const double &A, const point &B) { return point(B) *= A; }
    friend double operator*(const point &A, const point &B) { return A.x * B.x + A.y * B.y; }
    friend double operator/(const point &A, const point &B) { return A.x * B.y - A.y * B.x; }
    friend std::istream &operator>>(std::istream &A, point &B) { return A >> B.x >> B.y; }
    friend std::ostream &operator<<(std::ostream &A, const point &B) { return A << B.x << ' ' << B.y; }
    friend bool operator<=(const point &A, const point &B) { return A.x <= B.x && A.y <= B.y; }
    friend point min(const point &A, const point &B) { return point(std::min(A.x, B.x), std::min(A.y, B.y)); }
    friend point max(const point &A, const point &B) { return point(std::max(A.x, B.x), std::max(A.y, B.y)); }
    double angle() const { return std::atan2(y, x); }
    double abs() const { return std::sqrt(sqr(*this)); }
};
struct line
{
    point A, B;
    line() : A(), B() {}
    line(point A, point B) : A(A), B(B) {}
    point vec() const { return B - A; }
    double angle() const { return vec().angle(); }
    friend std::istream &operator>>(std::istream &A, line &B) { return A >> B.A >> B.B; }
    friend std::ostream &operator<<(std::ostream &A, const line &B) { return A << B.A << ' ' << B.B; }
    friend bool operator<(const line &A, const line &B)
    {
        return (B.angle() - A.angle() ?: (B.B - A.A) / (A.B - B.A)) > 0;
    }
    friend bool operator==(const line &A, const line &B) { return (A.B - A.A) / (B.B - B.A) == 0; }
};
struct circle
{
    point O;
    double r;
    friend std::istream &operator>>(std::istream &A, circle &B) { return A >> B.O >> B.r; }
    friend std::ostream &operator<<(std::ostream &A, const circle &B) { return A << B.O << ' ' << B.r; }
};
struct polygon : std::vector<point>
{
    using std::vector<point>::vector;
};
point projection(line a, point X) // 点X投影至直线a
{
    a.B -= a.A;
    X -= a.A;
    return a.A + (a.B * X) / (a.B * a.B) * a.B;
}
point reflection(line a, point X) // 点X关于直线a对称点
{
    a.B -= a.A;
    X -= a.A;
    return a.A + 2 * (a.B * X) / (a.B * a.B) * a.B - X;
}
std::string clockwise(line a, point X) // 点X相对线a位置
{
    a.B -= a.A;
    X -= a.A;
    if (a.B / X > 0)
        return "COUNTER_CLOCKWISE";
    if (a.B / X < 0)
        return "CLOCKWISE";
    if (a.B * X < 0)
        return "ONLINE_BACK";
    if ((a.A - a.B) * (X - a.B) < 0)
        return "ONLINE_FRONT";
    return "ON_SEGMENT";
}
bool orthogonal(line a, line b) // 直线a与直线b是否正交
{
    return std::abs(a.vec() * b.vec()) < eps;
}
bool parallel(line a, line b) // 直线a与直线b是否平行
{
    return std::abs(a.vec() / b.vec()) < eps;
}
int sign(double x) { return x < 0 ? -1 : x > 0; }
bool intersection(line a, line b) // 线段a与线段b是否相交
{
    if (std::abs(sign((b.A - a.A) / (a.B - a.A)) + sign((b.B - a.A) / (a.B - a.A))) == 2)
        return false;
    if (std::abs(sign((a.A - b.A) / (b.B - b.A)) + sign((a.B - b.A) / (b.B - b.A))) == 2)
        return false;
    return max(min(a.A, a.B), min(b.A, b.B)) <= min(max(a.A, a.B), max(b.A, b.B));
}
point cross(line a, line b) // 直线a与直线b的交点
{
    a.B -= a.A;
    b.A -= a.A;
    b.B -= a.A;
    return a.A + ((b.B - b.A) / b.A) / ((b.B - b.A) / a.B) * a.B;
}
double distance(line a, point X) // 点X与线段a的距离的平方
{
    a.B -= a.A;
    X -= a.A;
    if (X * a.B < 0)
        return sqr(X);
    if ((a.B - X) * a.B < 0)
        return sqr(a.B - X);
    return sqr(a.B / X) / sqr(a.B);
}
double distance(line a, line b) // 线段AB与线段CD的距离的平方
{
    if (intersection(a, b))
        return 0;
    return std::min({distance(a, b.A), distance(a, b.B), distance(b, a.A), distance(b, a.B)});
}
double area(polygon P) // 多边形P的面积
{
    double res = 0;
    for (std::size_t i = 0; i != P.size(); ++i)
        res += P[i] / P[(i + 1) % P.size()];
    return res / 2;
}
bool isConvex(polygon P) // 多边形P是否是凸的
{
    for (std::size_t i = 0; i != P.size(); ++i)
        if ((P[i] - P[(i + 1) % P.size()]) / (P[(i + 1) % P.size()] - P[(i + 2) % P.size()]) < 0)
            return false;
    return true;
}
std::string inPolygon(polygon P, point X) // 点X是否在多边形P中
{
    bool in = false;
    for (auto &i : P)
        i -= X;
    for (std::size_t i = 0; i != P.size(); ++i)
    {
        point A = P[i], B = P[(i + 1) % P.size()];
        if (clockwise(line(A, B), point()) == "ON_SEGMENT")
            return "ON";
        if (A.x < B.x)
            std::swap(A, B);
        in ^= A.x > 0 && B.x <= 0 && A / B > 0;
    }
    return in ? "IN" : "OUT";
}
polygon convex(polygon P) // 求点集P的凸包
{
    std::iter_swap(P.begin(), std::min_element(P.begin(), P.end(), [&](const point &A, const point &B)
                                               { return A.y == B.y ? A.x < B.x : A.y < B.y; }));
    point r = P[0];
    for (auto &i : P)
        i -= r;
    std::sort(P.begin() + 1, P.end(), [&](const point &A, const point &B)
              { return A / B == 0 ? sqr(A) < sqr(B) : A / B > 0; });
    std::size_t suf = 1;
    while (P[P.size() - suf - 1] / P[P.size() - suf] < eps)
        ++suf;
    std::sort(P.end() - suf, P.end(), [&](const point &A, const point &B)
              { return sqr(A) > sqr(B); });
    polygon Q;
    for (auto i : P)
    {
        while (Q.size() >= 2 && Q.end()[-2] / Q.back() + Q.back() / i + i / Q.end()[-2] < 0)
            Q.pop_back();
        Q.push_back(i);
    }
    for (auto &i : Q)
        i += r;
    return Q;
}
double diameter(polygon P) // 求凸多边形P的直径的平方
{
    double res = 0;
    P.insert(P.end(), P.begin(), P.end());
    for (std::size_t i = 0, j = 0; i != P.size(); ++i)
    {
        while ((P[j + 1] - P[i]) * (P[j + 1] - P[i]) > (P[j] - P[i]) * (P[j] - P[i]))
            ++j;
        res = std::max(res, sqr(P[j] - P[i]));
    }
    return res;
}
std::pair<std::vector<line>, polygon> halfPlaneIntersection(std::vector<line> l) // 半平面集的半平面交（如果存在一个凸多边形）
{
    std::sort(l.begin(), l.end());
    l.erase(std::unique(l.begin(), l.end()), l.end());
    std::deque<line> g;
    std::deque<point> h;
    for (const auto &i : l)
    {
        while (!h.empty() && clockwise(i, h.back()) == "CLOCKWISE")
            g.pop_back(), h.pop_back();
        while (!h.empty() && clockwise(i, h.front()) == "CLOCKWISE")
            g.pop_front(), h.pop_front();
        if (!g.empty())
        {
            if (h.empty() && g.back().angle() + PI <= i.angle())
                break;
            h.push_back(cross(g.back(), i));
        }
        g.push_back(i);
    }
    while (!h.empty() && clockwise(g.front(), h.back()) == "CLOCKWISE")
        g.pop_back(), h.pop_back();
    h.push_back(cross(g.back(), g.front()));
    return {std::vector<line>(g.begin(), g.end()), polygon(h.begin(), h.end())};
}
int circleIntersection(circle O, circle P) // 圆O与圆P公切线条数
{
    if (sqr(O.O - P.O) > sqr(O.r + P.r))
        return 4;
    if (sqr(O.O - P.O) == sqr(O.r + P.r))
        return 3;
    if (sqr(O.O - P.O) < sqr(O.r - P.r))
        return 0;
    if (sqr(O.O - P.O) == sqr(O.r - P.r))
        return 1;
    return 2;
}
circle incircle(point A, point B, point C) // 三角形ABC的内接圆
{
    double a = std::sqrt(sqr(B - C)), b = std::sqrt(sqr(A - C)), c = std::sqrt(sqr(B - A));
    return {1 / (a + b + c) * (a * A + b * B + c * C), std::abs(A / B + B / C + C / A) / (a + b + c)};
}
circle circum(point A, point B, point C) // 三角形ABC的外切圆
{
    double a = sqr(A), b = sqr(B), c = sqr(C);
    double S = (A / B + B / C + C / A) * 2;
    return {(~A * (b - c) + ~B * (c - a) + ~C * (a - b)) * (1 / S), std::sqrt(sqr(A - B) * sqr(B - C) * sqr(C - A)) / std::abs(S)};
}
bool iscross(circle O, line a) // 圆O与直线a是否有交
{
    a.A -= O.O;
    a.B -= O.O;
    a.A -= a.B;
    double delta = sqr(a.A * a.B) - sqr(a.A) * sqr(a.B) + sqr(a.A) * sqr(O.r);
    return delta >= 0;
}
line cross(circle O, line a) // 圆O与直线a的交点
{
    a.A -= O.O;
    a.B -= O.O;
    a.A -= a.B;
    double delta = sqr(a.A * a.B) - sqr(a.A) * sqr(a.B) + sqr(a.A) * sqr(O.r);
    assert(delta >= 0);
    delta = std::sqrt(delta);
    return {(-a.A * a.B + delta) / sqr(a.A) * a.A + a.B + O.O,
            (-a.A * a.B - delta) / sqr(a.A) * a.A + a.B + O.O};
}
line cross(circle O, circle P) // 圆O与圆P的交点
{
    point x = (sqr(O.r) - sqr(P.r) + sqr(P.O - O.O)) / (2 * sqr(P.O - O.O)) * (P.O - O.O);
    point y = std::sqrt(sqr(O.r) / sqr(P.O - O.O) - sqr((sqr(O.r) - sqr(P.r) + sqr(P.O - O.O))) / (4 * sqr(sqr(P.O - O.O)))) * ~(P.O - O.O);
    return {O.O + x - y, O.O + x + y};
}
line tangent(circle O, point X) // 点X过圆O的切点
{
    point c = O.O - X, delta = std::sqrt(sqr(c) - sqr(O.r)) * O.r * ~c;
    return {X + ((sqr(c) - sqr(O.r)) * c + delta) * (1 / sqr(c)), X + ((sqr(c) - sqr(O.r)) * c - delta) * (1 / sqr(c))};
}
std::vector<line> tangent(circle O, circle P) // 圆O与圆P的公切线
{
    static line tmp;
    bool flag = false;
    std::vector<line> res;
    auto push = [&](line x)
    { return flag ? res.push_back({x.B, x.A}) : res.push_back(x); };
    if (O.r > P.r)
        std::swap(O, P), flag = true;
    if (sqr(O.O - P.O) > sqr(O.r - P.r))
    {
        tmp = tangent({P.O, P.r - O.r}, O.O);
        push({O.O + ~(tmp.A - O.O) * (O.r / (tmp.A - O.O).abs()), tmp.A + ~(tmp.A - O.O) * (O.r / (tmp.A - O.O).abs())});
        push({O.O - ~(tmp.B - O.O) * (O.r / (tmp.B - O.O).abs()), tmp.B - ~(tmp.B - O.O) * (O.r / (tmp.B - O.O).abs())});
    }
    else if (sqr(O.O - P.O) == sqr(O.r - P.r))
        res.push_back({(O.O * P.r - P.O * O.r) * (1 / (P.r - O.r)), ~(P.O - O.O)});
    if (sqr(O.O - P.O) > sqr(O.r + P.r))
    {
        tmp = tangent({P.O, P.r + O.r}, O.O);
        push({O.O - ~(tmp.A - O.O) * (O.r / (tmp.A - O.O).abs()), tmp.A - ~(tmp.A - O.O) * (O.r / (tmp.A - O.O).abs())});
        push({O.O + ~(tmp.B - O.O) * (O.r / (tmp.B - O.O).abs()), tmp.B + ~(tmp.B - O.O) * (O.r / (tmp.B - O.O).abs())});
    }
    else if (sqr(O.O - P.O) == sqr(O.r + P.r))
        res.push_back({(O.O * P.r + P.O * O.r) * (1 / (O.r + P.r)), ~(P.O - O.O)});
    return res;
}
double areaIntersection(circle O, line a) // 圆O与三角形Oa的交的有向面积
{
    auto adjust = [](double x)
    {
        while (x > PI)
            x -= 2 * PI;
        while (x < -PI)
            x += 2 * PI;
        return x;
    };
    std::vector<point> p;
    p.push_back(a.A);
    p.push_back(a.B);
    if (iscross(O, a))
    {
        line tmp = cross(O, a);
        p.push_back(tmp.A);
        p.push_back(tmp.B);
    }
    std::sort(p.begin(), p.end(), [&](const point &A, const point &B)
              { return A * a.vec() < B * a.vec(); });
    p.erase(std::remove_if(p.begin(), p.end(), [&](const point &X)
                           { return X * a.vec() < a.A * a.vec() || X * a.vec() > a.B * a.vec(); }),
            p.end());
    for (auto &i : p)
        i -= O.O;
    double res = 0;
    for (std::size_t i = 1; i != p.size(); ++i)
        if (sqr(p[i - 1]) < sqr(O.r) + eps && sqr(p[i]) < sqr(O.r) + eps)
            res += p[i - 1] / p[i];
        else
            res += adjust(p[i].angle() - p[i - 1].angle()) * sqr(O.r);
    return res / 2;
}
double areaIntersection(circle O, circle P) // 圆O与圆P的交的面积
{
    auto adjust = [](double x)
    {
        while (x > 2 * PI)
            x -= 2 * PI;
        while (x < 0)
            x += 2 * PI;
        return x;
    };
    if (sqr(O.O - P.O) <= sqr(O.r - P.r))
        return sqr(std::min(O.r, P.r)) * PI;
    if (sqr(O.O - P.O) >= sqr(O.r + P.r))
        return 0;
    line tmp = cross(O, P);
    return (adjust((tmp.B - O.O).angle() - (tmp.A - O.O).angle()) * sqr(O.r) - (O.O / tmp.A + tmp.A / tmp.B + tmp.B / O.O) +
            adjust((tmp.A - P.O).angle() - (tmp.B - P.O).angle()) * sqr(P.r) - (P.O / tmp.B + tmp.B / tmp.A + tmp.A / P.O)) /
           2;
}