Alyona 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.

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$).