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

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

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

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

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

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

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

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

现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

Input

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

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

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

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

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

示初始战斗力和第一个攻击的城池。

Output

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

数量，后 m 行分别表示骑士  到 m 攻占的城池数量。

Sample Input

  -

Sample Output

Hint

 对于 % 的数据， <= n;m <= ;  <= fi<i;  <= ci <= n; -^ <= hi,vi,si <= ^;ai等于1或者2；
当 ai = 时，vi > ；保证任何时候骑士战斗力值的绝对值不超过 ^。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn],rt[maxn],cnt,tot;

int a[maxn],c[maxn],dep[maxn],die[maxn],ans[maxn];

ll h[maxn],p[maxn],v[maxn];

struct in{

    int from,dis,l,r; ll key,ly1,ly2;

}s[maxn];

void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; }

int make_tree(int u)

{

    tot++; s[tot].key=p[u]; s[tot].from=u; s[tot].dis=;

    s[tot].l=s[tot].r=s[tot].ly2=; s[tot].ly1=;

    return tot;

}

void push_down(int u)

{

    if(s[u].ly1>) {

        if(s[u].l) s[s[u].l].key*=s[u].ly1, s[s[u].l].ly2*=s[u].ly1, s[s[u].l].ly1*=s[u].ly1;

        if(s[u].r) s[s[u].r].key*=s[u].ly1, s[s[u].r].ly2*=s[u].ly1, s[s[u].r].ly1*=s[u].ly1;

        s[u].ly1=;

    }

    if(s[u].ly2) {

        if(s[u].l) s[s[u].l].key+=s[u].ly2, s[s[u].l].ly2+=s[u].ly2;

        if(s[u].r) s[s[u].r].key+=s[u].ly2, s[s[u].r].ly2+=s[u].ly2;

        s[u].ly2=;

    }

}

int merge(int x,int y)

{

    push_down(x); push_down(y);

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

    if(s[x].key>s[y].key) swap(x,y);

    s[x].r=merge(s[x].r,y);

    if(s[s[x].r].dis>s[s[x].l].dis) swap(s[x].l,s[x].r);

    s[x].dis=s[s[x].r].dis+;

    return x;

}

void dfs(int u,int f)

{

    dep[u]=dep[f]+;

    for(int i=Laxt[u];i;i=Next[i]){

        dfs(To[i],u);

        rt[u]=merge(rt[u],rt[To[i]]);

    }

    while(rt[u]&&s[rt[u]].key<h[u]) {

        ans[s[rt[u]].from]=dep[c[s[rt[u]].from]]-dep[u];

        rt[u]=merge(s[rt[u]].l,s[rt[u]].r);

        die[u]++;

    }

    if(!rt[u]) return ;

    if(u==){

        while(rt[u]){

            ans[s[rt[u]].from]=dep[c[s[rt[u]].from]]-dep[u]+;

            rt[u]=merge(s[rt[u]].l,s[rt[u]].r);

         }

    }

    else if(a[u]) s[rt[u]].key*=v[u], s[rt[u]].ly1*=v[u];

    else s[rt[u]].key+=v[u], s[rt[u]].ly2+=v[u];

}

int main()

{

    int N,M,u,i,j;

    scanf("%d%d",&N,&M);

    for(i=;i<=N;i++) scanf("%lld",&h[i]);

    for(i=;i<=N;i++){

        scanf("%d%d%lld",&u,&a[i],&v[i]);

        add(u,i);

    }

    for(i=;i<=M;i++){

         scanf("%lld%d",&p[i],&c[i]);

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

    }

    dfs(,);

    for(i=;i<=N;i++) printf("%d\n",die[i]);

    for(i=;i<=M;i++) printf("%d\n",ans[i]);

    return ;

}