You are given a tree of size \(N\). The tree isrooted at \(1 \) and each node \(i\ (1 \le i\le N)\) contains a value \(A_i\).

You are also given an array \(K \) of size \(N\). For each node \(i\ (1 \le i\le N)\), you are required to determine the distance to the closest node \(j\) in the subtree of \(i\) such that \(\mid A_i - A_j \mid \ge K_i\).

Note

Distance between two nodes is calculated as the shortest path between them and it is represented as the number of edges
\(i \) also lies in its subtree

Input format

First line: An integer \(N\)
Second line: \(N\) space-separated integers denoting the elements of \(A \)
Third line: \(N\) space-separated integers denoting the elements of \(K\)
Next \(N-1 \) lines: Two integers \(u \) and \(v \) \((1 \le u,v \le N , u!=v)\) denoting an edge between them

Output format

Print \(N\) lines representing the answer. Here, \(i^{th}\) line contains the distance to the closest node \(j\) in subtree \(i \) that satisfies the condition. If no nodes satisfy the condition, then print \(-1\).

Constraints

\(1 \le N \le 200000\)

\(1 \le A_i \le 10^9\)

\(0 \le K_i \le 10^9\)