小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。

这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，

其中 fi <i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其

中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。

每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可

以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力

将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。

除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城

的结果。

第 1 行包含两个正整数 n;m，表示城池的数量和骑士的数量。

第 2 行包含 n 个整数，其中第 i 个数为 hi，表示城池 i 的防御值。

第 3 到 n +1 行，每行包含三个整数。其中第 i +1 行的三个数为 fi;ai;vi，分别表示管辖

这座城池的城池编号和两个战斗力变化参数。

第 n +2 到 n + m +1 行，每行包含两个整数。其中第 n + i 行的两个数为 si;ci，分别表

输出 n + m 行，每行包含一个非负整数。其中前 n 行分别表示在城池 1 到 n 牺牲的骑士

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ls ch[x][0]

 #define rs ch[x][1]

 #define int long long

 #define M 300010

 using namespace std;

 int read()

 {

     char ch=getchar();int x=,f=;

     while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

     return x*f;

 }

 int n,m,num;

 int head[M],rt[M],a[M],v[M],dis[M],val[M],tag1[M],tag2[M],ch[M][];

 int fa[M],deep[M],kill[M],dead[M],c[M],h[M];

 struct point{int to,next;}e[M<<];

 void add(int from,int to)

 {

     e[++num].next=head[from];

     e[num].to=to;

     head[from]=num;

 }

 void pushdown(int x,int t1,int t2)

 {

     val[x]*=t1,val[x]+=t2;

     tag1[x]*=t1;tag2[x]*=t1,tag2[x]+=t2;

 }

 void push(int x)

 {

     pushdown(ls,tag1[x],tag2[x]);

     pushdown(rs,tag1[x],tag2[x]);

     tag1[x]=,tag2[x]=;

 }

 int merge(int x,int y)

 {

     if(!x||!y) return x+y;

     push(x),push(y);

     if(val[x]>val[y]) swap(x,y);

     ch[x][]=merge(rs,y);

     if(dis[ls]<dis[rs]) swap(ls,rs);

     dis[x]=dis[rs]+;

     return x;

 }

 void dfs(int x)

 {

     deep[x]=deep[fa[x]]+;

     for(int i=head[x];i;i=e[i].next)

     {

         int to=e[i].to;dfs(to);

         rt[x]=merge(rt[x],rt[to]);

     }

     while(rt[x]&&val[rt[x]]<h[x])

     {

         push(rt[x]);

         dead[x]++;

         kill[rt[x]]=deep[c[rt[x]]]-deep[x];

         rt[x]=merge(ch[rt[x]][],ch[rt[x]][]);

     }

     if(a[x]) pushdown(rt[x],v[x],);

     else pushdown(rt[x],,v[x]);

 }

 #undef int

 int main()

 {

     #define int long long

     n=read();m=read();

     for(int i=;i<=n;i++) h[i]=read();

     for(int i=;i<=n;i++)

     {

         fa[i]=read(),a[i]=read();

         v[i]=read(),add(fa[i],i);

     }

     for(int i=;i<=m;i++)

     {

         val[i]=read(),c[i]=read();

         tag1[i]=,tag2[i]=;

         rt[c[i]]=merge(rt[c[i]],i);

     }

     dfs();

     while(rt[])//如果一直没死

     {

         push(rt[]);

         kill[rt[]]=deep[c[rt[]]];

         rt[]=merge(ch[rt[]][],ch[rt[]][]);

     }

     for(int i=;i<=n;i++) printf("%lld\n",dead[i]);

     for(int i=;i<=m;i++) printf("%lld\n",kill[i]);

     return ;

 }