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$