Migrated from Lutece 3156 猫树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：可并堆

小$w$最近在玩怪猎。

现在小$w$手下的$m$只猫想要占领一棵有$n$个节点的树。

这棵树节点编号为$1\sim n$，除$1$号城池外，城池$i$会受到另一个节点$f_i$的管辖，其中$f_i<i$。

这$m$只猫用$1\sim m$的整数表示，其中第$i$只猫的战斗力为$a_i$，准备第一个占领的节点为$b_i$。

每个节点上有一只龙，血量为$h_i$，如果一只猫的战斗力大于等于龙的血量，那么它可以打败这条龙并占领这个节点，否则猫猫会马上逃跑。猫猫在打败龙后，信心增长，战斗力会发生变化，然后继续攻击管辖这个节点的节点，直到逃跑或占领$1$号节点。

除$1$号节点外，每个节点会给出一个战斗力变化参数$({ty}_i,v_i)$，如果${ty}_i=0$，那么猫猫的战斗力会增加$v_i$，如果${ty}_i=1$，那么猫猫的战斗力会乘以$v_i$。

注意每只猫是单独计算的，也就是说，每只猫的占领结果不会影响到其他猫。

现在小$w$想知道对于每个节点，有多少只猫会在这里逃跑；对于每只猫，它能占领多少个节点。

Input

第1行包含两个正整数$n,m$，表示节点和猫的数量。

第2行包含$n$个正整数，其中第$i$个数为$h_i$，表示第$i$个节点上的龙的血量.。

第$3\sim n+1$行，每行包含三个整数。其中第$i+1$行为$f_i,{ty}_i,v_i$，表示第$i$个节点的管辖节点编号和战斗力变化参数。

第$n+2\sim n+m+1$行，每行包含两个整数。其中第$n+i$行的两个数为$a_i,b_i$，分别表示第$i$只猫的初始战斗力和第一个占领的节点。

Output

输出$n+m$行，每行包含一个非负整数。其中前$n$行分别表示在城池$1\sim n$逃跑的猫猫数量，后$m$行分别表示猫猫$1\sim m$占领的节点数量。

Samples

5 5
50 20 10 10 30
1 1 2
2 0 5
2 0 -10
1 0 10
20 2
10 3
40 4
20 4
35 5

2
2
0
0
0
1
1
3
1
1

Constraints

$1\leq n,m\leq 3\times 10^5,0\leq h_i,a_i\leq 10^9,-10^{9}\leq v_i\leq 10^9,1\leq f_i< i,1\leq b_i\leq n,{ty}_i\in \{0,1\}$，保证${ty}_i=1$时，$v_i>0$。保证任何时候猫的战斗力不会超过$10^{18}$。

Resources

2024 UESTC ICPC Training for Data Structure