Description

Xiao Mingming recently got a new board game. In the game, you need to use $m$ knights to conquer $n$ cities.

The $n$ cities are numbered from $1$ to $n$. Except for city $1$, each city $i$ is governed by another city $f_i$ with $f_i<i$. In other words, all cities form a rooted tree.

The $m$ knights are numbered from $1$ to $m$, where knight $i$ has initial combat power $s_i$, and his first target city is $c_i$.

Each city has a defense value $h_i$. If a knight's combat power is greater than or equal to the city's defense value, then the knight can capture that city; otherwise, the capture fails and the knight will fall at that city. After capturing a city, the knight's combat power will change, and then he continues to attack the city that governs this city (its parent), until he captures city $1$, or dies.

Except for city $1$, each city $i$ provides a combat-power change parameter $(a_i, v_i)$. If $a_i=0$, after capturing city $i$, the knight's combat power increases by $v_i$; if $a_i=1$, after capturing city $i$, the combat power is multiplied by $v_i$.

Note that each knight is simulated independently. That is, when a knight attacks a city, regardless of the outcome, it does not affect the result of other knights attacking this city.

Now the problem is: for each city, output how many knights die here; and for each knight, output how many cities he captures.

Input Format

The first line contains two positive integers $n,m$, the numbers of cities and knights.

The second line contains $n$ integers, where the $i$-th number is $h_i$, the defense value of city $i$.

Lines $3$ to $n+1$: for each city $i$ from $2$ to $n$, line $i+1$ contains three integers $f_i,a_i,v_i$, denoting the governing (parent) city of city $i$ and the two combat-power change parameters.

Lines $n+2$ to $n+m+1$: for each knight $i$ from $1$ to $m$, line $n+1+i$ contains two integers $s_i,c_i$, the initial combat power and the first city to attack.

Output Format

Output $n+m$ lines, each containing a nonnegative integer. The first $n$ lines give, for cities $1$ to $n$, the number of knights who die there; the last $m$ lines give, for knights $1$ to $m$, the number of cities they capture.

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

Hint

For $100\%$ of the testdata, $1\le n,m\le 3\times 10^5$, $-10^{18}\le h_i,v_i,s_i\le 10^{18}$, $1\le f_i<i$, $1\le c_i\le n$, $a_i\in\{0,1\}$. It is guaranteed that when $a_i=1$, $v_i>0$, and that at any time the absolute value of a knight's combat power does not exceed $10^{18}$.

Translated by ChatGPT 5