Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Alyona and a tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlyona has a tree with *n* vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex *i* she wrote *a*_{i}. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define *dist*(*v*, *u*) as the sum of the integers written on the edges of the simple path from *v* to *u*.

The vertex *v* controls the vertex *u* (*v* ≠ *u*) if and only if *u* is in the subtree of *v* and *dist*(*v*, *u*) ≤ *a*_{u}.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex *v* what is the number of vertices *u* such that *v* controls *u*.

Input

The first line contains single integer *n* (1 ≤ *n* ≤ 2·10^{5}).

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) — the integers written in the vertices.

The next (*n* - 1) lines contain two integers each. The *i*-th of these lines contains integers *p*_{i} and *w*_{i} (1 ≤ *p*_{i} ≤ *n*, 1 ≤ *w*_{i} ≤ 10^{9}) — the parent of the (*i* + 1)-th vertex in the tree and the number written on the edge between *p*_{i} and (*i* + 1).

It is guaranteed that the given graph is a tree.

Output

Print *n* integers — the *i*-th of these numbers should be equal to the number of vertices that the *i*-th vertex controls.

Examples

Input

5

2 5 1 4 6

1 7

1 1

3 5

3 6

Output

1 0 1 0 0

Input

5

9 7 8 6 5

1 1

2 1

3 1

4 1

Output

4 3 2 1 0

Note

In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn't mean the vertex 1 controls the vertex 5).

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2019 04:16:37 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|