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 ai. 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) ≤ au.

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·105).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the integers written in the vertices.

The next (n - 1) lines contain two integers each. The i-th of these lines contains integers pi and wi (1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) — the parent of the (i + 1)-th vertex in the tree and the number written on the edge between pi 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).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class p0740D{
	static int N;
	static int[] subtreeSize, timesAdded, preorder, hEdge;
	static int[][] anc;
	static long[] a, edge, sum;
	static ArrayList<Integer>[] nexts;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] line;
		
		// input N
		line = br.readLine().split(" ");
		N = Integer.parseInt(line[0]);
		
		// input a_i for all i
		line = br.readLine().split(" ");
		a = new long[N];
		for(int n=0;n<N;n++) a[n] = Integer.parseInt(line[n]);
		
		// input parent and weight for each nonroot node
		anc = new int[N][20]; for(int n=0;n<N;n++) Arrays.fill(anc[n], -1);
		nexts = new ArrayList[N]; for(int n=0;n<N;n++) nexts[n] = new ArrayList<>();
		edge = new long[N];
		for(int n = 1; n < N; n++){
			line = br.readLine().split(" ");
			int P = Integer.parseInt(line[0])-1;
			long W = Integer.parseInt(line[1]);
			anc[n][0] = P;
			nexts[P].add(n);
			edge[n] = W;
		}
		
		// get all the sizes of each subtree
		subtreeSize = new int[N]; Arrays.fill(subtreeSize, 1);
		timesAdded = new int[N];
		ArrayDeque<Integer> q = new ArrayDeque<>(N);
		for(int n=0;n<N;n++){
			if(nexts[n].size() == 0){
				q.offer(n);
			}
		}
		while(!q.isEmpty()){
			int poll = q.poll().intValue();
			if(poll == 0) break;
			subtreeSize[anc[poll][0]] += subtreeSize[poll];
			timesAdded[anc[poll][0]]++;
			if(timesAdded[anc[poll][0]] == nexts[anc[poll][0]].size()){
				q.offer(anc[poll][0]);
			}
		}
		
		// do some more precomp stuff
		preorder = new int[N];
		sum = new long[N];
		precomp(0, 0, 0L);
		
		// heavy light decomp
		hEdge = new int[N];
		HLD(0, true, true);
		hEdge[0] = -1;
		
//		for(int[] ar : anc) System.out.println(Arrays.toString(ar));
//		System.out.println(Arrays.toString(preorder));
//		System.out.println(Arrays.toString(sum));
//		System.out.println(Arrays.toString(hEdge));
//		System.out.println(Arrays.toString(subtreeSize));
		
		// make a fenwick tree
		Fenwick fenwick = new Fenwick(N);
		
		// for each nonroot node, update fenwick tree
		// take advantage of heavy edges!!
		for(int n=1;n<N;n++){
			// find out how many light edges/heavy paths you can skip over
			int temp = n;
			long sumSoFar = 0;
			while(temp > 0 && sum[temp] - sum[hEdge[temp]] + sumSoFar <= a[n]){
				sumSoFar += sum[temp] - sum[hEdge[temp]];
				fenwick.modifyInclRange(preorder[hEdge[temp]], preorder[anc[temp][0]], 1);
				temp = hEdge[temp];
			}
			// if temp is the root or hEdge[temp] is just temp's parent, we can just continue
			if(hEdge[temp] == anc[temp][0]) continue;
			// otherwise we must stop somewhere on this heavy path
			int lastTemp = temp;
			for(int d = 19; d >= 0; d--){
				if(anc[temp][d] == -1) continue;
				if(sum[temp] - sum[anc[temp][d]] + sumSoFar <= a[n]){
					sumSoFar += sum[temp] - sum[anc[temp][d]];
					temp = anc[temp][d];
				}
			}
//			System.out.println("for "+n+": "+temp+" "+lastTemp);
			// now we can update the fenwick tree again
			fenwick.modifyInclRange(preorder[temp], preorder[anc[lastTemp][0]], 1);
		}
		
		// query the fenwick tree over and over again to get the number of nodes each node controls
		StringBuilder sb = new StringBuilder();
		for(int n=0;n<N;n++){
			sb.append(fenwick.rsq(preorder[n])).append(' ');
		}
		
		System.out.println(sb.toString().trim());
	}
	static class Fenwick{
		long[] arr;
		Fenwick(int len){
			arr = new long[len];
		}
		long rsq(int i){
			long sum = 0;
			do{
				sum += arr[i];
				i = dep(i);
			} while(i != -1);
			return sum;
		}
		void modify(int i, long amount){
			while(i < arr.length){
				arr[i] += amount;
				i += ((~i) & (-(~i)));
			}
		}
		void modifyInclRange(int i, int j, long amount){
			if(i > j) return;
			modify(i, amount);
			if(j < arr.length-1) modify(j+1, -amount);
//			System.out.println("Modified "+i+" through "+j+":");
//			for(int n=0;n<arr.length;n++){
//				System.out.print(rsq(n)+" ");
//			}System.out.println();
		}
		int dep(int a){
			a++;
			return a - (a & (-a)) - 1;
		}
	}
	static Comparator<Integer> sizeSort = new Comparator<Integer>(){
		@Override
		public int compare(Integer o1, Integer o2){
			return subtreeSize[o2.intValue()] - subtreeSize[o1.intValue()];
		}
	};
	static void HLD(int index, boolean isHeavy, boolean isFirstHeavy){
		if(index != 0){
			if(!isHeavy){
				hEdge[index] = anc[index][0];
				for(int i = 0; i < nexts[index].size(); i++){
					if(i == 0) HLD(nexts[index].get(i).intValue(), true, true);
					else HLD(nexts[index].get(i).intValue(), false, false);
				}
			}
			else if(isHeavy && isFirstHeavy){
				hEdge[index] = anc[index][0];
				for(int i = 0; i < nexts[index].size(); i++){
					if(i == 0) HLD(nexts[index].get(i).intValue(), true, false);
					else HLD(nexts[index].get(i).intValue(), false, false);
				}
			}
			else{
				hEdge[index] = hEdge[anc[index][0]];
				for(int i = 0; i < nexts[index].size(); i++){
					if(i == 0) HLD(nexts[index].get(i).intValue(), true, false);
					else HLD(nexts[index].get(i).intValue(), false, false);
				}
			}
		}
		else for(int i = 0; i < nexts[index].size(); i++){
			if(i == 0) HLD(nexts[index].get(i).intValue(), true, false);
			else HLD(nexts[index].get(i).intValue(), false, false);
		}
	}
	static int precomp(int index, int pre, long sumSoFar){
		// update sum
		preorder[index] = pre;
		sum[index] = sumSoFar;
		// generate anc table
		for(int d = 0; anc[index][d] != -1; d++){
			anc[index][d+1] = anc[anc[index][d]][d];
		}
		// sort children by their subtree size
		Collections.sort(nexts[index], sizeSort);
		// call children
		for(int i = 0; i < nexts[index].size(); i++){
			int ch = nexts[index].get(i);
			pre = precomp(ch, pre+1, sumSoFar + edge[ch]);
		}
		return pre;
	}
}

/*

10
5 5 5 5 5 5 5 5 5 5
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1

4
2 2 2 2
1 1
2 1
2 1

5
2 2 2 2 2
1 1
2 1
2 1
3 1

5
2 2 2 2 2
1 1
2 1
3 1
3 1

7
2 2 2 2 2 2 2
1 1
2 1
3 1
3 1
4 1
5 1


*/