Knight Conquest

You are given a tree structure of n cities numbered from 1 to n (city 1 is the root). For every city i (where 2 ≤ i ≤ n), you are given its parent city f_i (with 1 ≤ f_i < i), so that the cities form a rooted tree. Each city i has a defense value \(h_i\). There are also m knights numbered from 1 to m. The i-th knight has an initial battle power \(s_i\) and his first target city is \(c_i\>.

The knights try to capture cities in the following way. A knight starting at city \(c_i\) attempts to capture that city. If his current battle power is at least the defense value of that city (i.e. \(s \ge h_{\text{city}}\)), then he captures the city. Otherwise, the knight fails to capture the city and is sacrificed there. When a knight successfully captures a city, if the city is not city 1, it will alter his battle power using a provided parameter \((a, v)\) associated with that city. Specifically, if \(a=0\) then his battle power is increased by \(v\) (i.e. \(s=s+v\)), and if \(a=1\) then his battle power is multiplied by \(v\) (i.e. \(s=s\times v\)). After capturing a city (and updating his battle power accordingly), if the captured city is not city 1, the knight moves to the parent city (i.e. from city \(i\) to city \(f_i\)) and repeats the process. Once a knight captures city 1, his journey ends successfully.

Your task is to determine two things:

• For each city, count how many knights were sacrificed while attempting to capture that city.
• For each knight, count the number of cities he captured before his journey ended (either by being sacrificed or by capturing city 1).

Input/Output Details are described below.

inputFormat

The input is given as follows:

 n m
 h1 h2 ... hn
 f2 a2 v2
 f3 a3 v3
 ...
 f_n a_n v_n
 s1 c1
 s2 c2
 ...
 s_m c_m

Here:

• n is the number of cities and m is the number of knights.
• \(h_i\) is the defense value of city \(i\) (1 ≤ i ≤ n).
• For every city \(i\) from 2 to \(n\), \(f_i\) (with 1 ≤ \(f_i\) < i) is the city that governs city \(i\), and \((a_i, v_i)\) is the pair that determines how a knight's battle power changes after capturing city \(i\). If \(a_i = 0\), the knight's battle power increases by \(v_i\), and if \(a_i = 1\), his battle power is multiplied by \(v_i\).
• Each knight is described by two numbers: \(s_i\), his initial battle power, and \(c_i\), the first city he attacks.

outputFormat

Output two lines:

• The first line contains n integers. The \(i\)-th integer is the number of knights sacrificed at city \(i\>.
• The second line contains m integers, where the \(i\)-th integer is the number of cities captured by knight \(i\>.

Separate numbers by spaces.

sample

3 2
10 5 3
1 0 5
1 1 2
5 2
10 3

0 0 0
2 2