我只想到了n根号(nlog)log的分块，感谢出题人教了我如何n根号log。

(假设分k块)

每个块内都排好序。

加的时候
整块的就打标记 O(k)
零散的，
考虑打标记后，没打标记的和打了标记的部分顺序都还是不变，
遍历一遍原来排好的顺序，就能得到这两个部分，之后归并一下就可以了。O(n/k)

求k大
先二分 转为check一个区间有多少数比一个数小。

按普通的想法
整块的二分 O(klog)
零散的暴力 O(n/k)
所以一次复杂度是O(klog^2+nlog/k)
k取根号(n/log),总复杂度就是O(n根号(nlog)log)

注意到，check零散的时间是O(nlog/k)，这还可以优化。
首先，用遍历一遍原来顺序的方法 O(n/k)把两个零散的各自排序。
之后check的时候就可以二分了，O(log^2)
所以一次复杂度变成O(klog^2+n/k)
k取根号n/log,总复杂度就是O(n根号nlog)

还有一个方法，是跟值域有关的。

因为值域小了，就可以处理出每个块的前缀和

分块使得
1 每个块max-min<=x1*len
2 块的大小也不超过x2
3 块尽量大

如果不考虑2的话 块是n/x1个的
因为所有相邻两数的差的和是nlen的 因为n次区间加，每次加len
而相邻两块的max-min>x1len
说明相邻两块所有相邻两数的差>max-min>x1len
所以块数<nlen/x1*len=n/x1

现在再把2考虑进来 相当于说一些大于x2的块要被拆掉
设大于x2的块的大小-x2的和是sum 那么每拆一次 sum-=x2
所以最多拆n/x2次

所以块数是n/x1+n/x2的。
因为所有块max-min的和<nlen，所以build的时间是nlen

check的时候
整块就可以O(1)
零散的暴力 就是x2
时间O(log*(n/x1+n/x2+x2))

加的时候整块打标记，O(n/x1+n/x2)
零散的暴力重算块的前缀和,O(x2+x1*len)

注意根号次加法后，块的max-min可能又大了根号*len，

这个时候要再重构一次分块。

时间(根号nlen)

x1,x2应该都要取根号

总时间O(n根号log+n根号len)

因为感觉第一种比较好写 我只写了第一种

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

#define mid (l+r>>1)

const int ch_top=10000000;
char ch[ch_top],*now_r=ch,*now_w=ch-1;
int read()
{
    while(*now_r<'0')++now_r;
    int x=*now_r-'0';
    while(*++now_r>='0') x=x*10+*now_r-'0';
    return x; 
}
void write(int x)
{
    static char st[20];static short top;
    if(!x)*++now_w='0';
    else
    {
        for(;x;x/=10)st[++top]='0'+x%10;
        for(;top;--top)*++now_w=st[top];
    }
    *++now_w='\n';
}

const int N=100005,L=1500,K=N/L+5;
int f[N],w[N];vector<int>son[N];
typedef vector<int>::iterator ii;
int a[N],b[N];//b[i]是块排好序后的人 

int q[N],t,qa[N],la,qb[N],lb;
void merge_to(int *q)
{
    if(!lb) { memcpy(q+1,qa+1,la*sizeof(int));return ; }
    if(!la) { memcpy(q+1,qb+1,lb*sizeof(int));return ; }
    t=0;
    int ha=1,hb=1;
    for(;;)
    if(a[qa[ha]]<a[qb[hb]])
    {
        q[++t]=qa[ha];
        if(++ha>la) 
        {
            do
            {
                q[++t]=qb[hb];
            }while(++hb<=lb);
            break;
        }
    }
    else
    {
        q[++t]=qb[hb];
        if(++hb>lb) 
        {
            do
            {
                q[++t]=qa[ha];
            }while(++ha<=la);
            break;
        }
    }
}

int kl[K],kr[K],ad[K];
bool a_xiao(int x,int y)
{
    return a[x]<a[y];
}

void chmin(int &x,int y)
{
    if(x>y)x=y;
}
void chmax(int &x,int y)
{
    if(x<y)x=y;
}

int dfn[N],out[N],tot;
void dfs(int x,int fr,int now)
{
    now+=w[x];
    a[dfn[x]=++tot]=now;
    for(ii it=son[x].begin();it!=son[x].end();++it)
     dfs(*it,x,now);
    out[x]=tot;
}

int nl,nr;
int erfen(int *q,int t,int now)
{
    if(a[q[1]]>now)return 0;
    if(a[q[t]]<=now)return t;
    int l=1,r=t;
    while(l+1!=r)
    if(a[q[mid]]<=now) l=mid;
    else r=mid;
    return l;
}
int xiao_deng(int now)
{
   int ans=erfen(qa,la,now)+erfen(qb,lb,now);
   for(int k=nl+1;k<nr;++k) ans+=erfen(b+kl[k]-1,L/*kr[k]-kl[k]+1*/,now-ad[k]);
   return ans;
} 

void down(int k)
{
    int x=ad[k];
    if(!x)return ;
    for(int i=kl[k];i<=kr[k];++i) a[i]+=x;
    ad[k]=0;
}

int main()
{
    //freopen("1.in","r",stdin);freopen("3.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    int n=read(),m=read(),i,k;
    read();
    for(i=2;i<=n;++i)
    {
        son[f[i]=read()].push_back(i);
        w[i]=read();
    }

    dfs(1,0,0);

    tot=(n-1)/L;
    for(i=0;i<=tot+1;++i) {kl[i]=i*L+1;kr[i]=(i+1)*L;}
    kr[tot]=n;

    for(i=1;i<=n;++i)b[i]=i;
    for(k=0;k<=tot;++k)
        sort(b+kl[k],b+kr[k]+1,a_xiao);

    while(m--)
    {
        int type=read(),x=read();
        int ql=dfn[x],qr=out[x]; 
        //int ql=read(),qr=read();
        x=read();
        nl=(ql-1)/L;nr=(qr-1)/L;
        if(type==1)
        {
            int len=qr-ql+1;
            if(len<x) { *++now_w='-';*++now_w='1';*++now_w='\n';continue; }  
            down(nl);down(nr);
            if(len<=L*2)
            {
                down(nl+1);
                memcpy(q,a+ql,len*sizeof(int));
                nth_element(q,q+x-1,q+len);
                write(q[x-1]);
                continue;
            }
            else
            {
                la=0;
                for(i=kl[nl];i<=kr[nl];++i)
                if(b[i]>=ql) qa[++la]=b[i];
                lb=0;
                for(i=kl[nr];i<=kr[nr];++i)
                if(b[i]<=qr) qb[++lb]=b[i];
                //merge_to(q);

                int l=min(a[qa[1]],a[qb[1]]),r=max(a[qa[la]],a[qb[lb]]);
                for(k=nl+1;k<nr;++k) 
                {
                  chmin(l,a[b[kl[k]]]+ad[k]);
                  chmax(r,a[b[kr[k]]]+ad[k]); 
                }
                if(xiao_deng(l)>=x) { write(l);continue; }
                while(l+1!=r)
                {
                    if(xiao_deng(mid)>=x) r=mid;
                    else l=mid;
                }
                write(r);
            }
        }
        else
        {
            if(nl==nr)
            {
                for(i=ql;i<=qr;++i) a[i]+=x;
                la=lb=0;
                for(i=kl[nl];i<=kr[nl];++i) 
                if(b[i]>=ql&&b[i]<=qr) qa[++la]=b[i];
                else qb[++lb]=b[i];
                merge_to(b+kl[nl]-1);
                continue;
            }
            for(k=nl+1;k<nr;++k) ad[k]+=x;

            for(i=ql;i<=kr[nl];++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nl];i<=kr[nl];++i)
            if(b[i]>=ql) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nl]-1);

            for(i=kl[nr];i<=qr;++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nr];i<=kr[nr];++i)
            if(b[i]<=qr) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nr]-1);
        }
    }
    fwrite(ch,1,now_w-ch+1,stdout);
}