N. Tree Signals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Usopp and Robin are analyzing a massive island shaped like a rooted tree with $$$n$$$ vertices. The root is vertex 1. Each branch (edge) connecting the vertices has an integer value representing the wind speed, and each vertex $$$v$$$ has a wind tolerance $$$k_{v}$$$.

Usopp can shoot a signal flare from a vertex $$$u$$$ to a descendant $$$v$$$ if the difference between the maximum and minimum wind speeds (edge values) on the path from $$$u$$$ to $$$v$$$ is at most the receiver's tolerance $$$k_{v}$$$:

max(w on the path from u to v) - min(w on the path from u to v) $$$\le k_{v}$$$.

Robin notes that the tolerance used here belongs to the receiver $$$v$$$, not to the sender $$$u$$$.

If $$$u=v$$$, the path contains zero edges. In this case, the difference is defined as 0, so every vertex can successfully receive a signal from itself.

For every vertex $$$u$$$, find how many descendants ($$$u$$$ included) can receive a signal from $$$u$$$.

Note: a descendant of $$$u$$$ is any node $$$v$$$ in the subtree of $$$u$$$, including node $$$u$$$

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \times 10^{5}$$$) — the number of vertices in the rooted tree. The root is vertex 1.

The second line of each test case contains $$$n$$$ integers $$$k_{1}, k_{2}, \dots, k_{n}$$$ ($$$0 \le k_{i} \le 10^{9}$$$) — the tolerance of each vertex.

For each $$$i$$$ from 2 to $$$n$$$, the next line contains two integers $$$p_{i}$$$ and $$$w_{i}$$$ ($$$1 \le p_{i} \lt i$$$, $$$0 \le w_{i} \le 10^{9}$$$) — the parent of vertex $$$i$$$ and the wind speed value on the edge between $$$p_{i}$$$ and $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.

Output

For each test case, output $$$n$$$ integers on a single line. The $$$u$$$-th integer must be the number of descendants that can receive a signal from vertex $$$u$$$.

Example
Input
1
4
0 0 0 0
1 5
1 7
2 6
Output
3 2 1 1
Note

Vertex 1 reaches itself, vertex 2, and vertex 3. It does not reach vertex 4, because the values on the path to vertex 4 are 5 and 6, and their difference is greater than $$$k_{4}=0$$$.