暂无测试数据。

小 Z 是一个非常非常菜的 oi 选手。

某天，小 Z 想到了一个有趣的问题：

给定一棵 $n$ 个点的有根树 $T$，这 $n$ 个点分别编号为 $1 \ldots n$，其中点 $1$ 是树根，点 $i$ 的权值为 $a_i$，保证不同点的权值不同。对于有限集合 $S \subseteq Z$，定义 $f(S)$ : 如果 $\lvert S \rvert \le 1$ 则 $f(S) = -1$；否则，把 $S$ 中的元素从小到大排序后，$f(S)$ 为相邻两数差的绝对值的最大值。

形式化地：

$$\displaystyle f(S):= \begin{cases} -1& \lvert S \rvert \le 1\\ \max \{\lvert x-y\rvert\mid x,y \in S\wedge \neg (\exists z \in S, x<z<y)\}& \lvert S \rvert > 1 \end{cases} $$

小 Z 想知道，对于每个点 $u$，设集合 $S_u$ 为所有不是 $u$ 的祖先（$u$ 本身也是 $u$ 的祖先）也不是 $u$ 的后代的节点（这里 $u$ 的后代是指 $u$ 的子树中的所有节点）的权值构成的集合，那么 $f(S_u)$ 的值是多少？

小 Z 并不会做这个问题，为了在问出这个问题的算法的同时不被大佬们嘲讽，小 Z 决定假装自己会做，然后用这题去考小 T。小 T 是一个非常非常强的 oi 选手，他随手秒掉了这题，并向小 Z 询问这道题的标算。然而小 Z 并不知道如何解决这个问题，如果他说不出这道题的标算，就会被大佬们嘲讽。于是他只好求助于你，希望你能帮他解决这个问题。

输入格式

第一行一个正整数 $n$，表示树上节点的数量。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$，具体意义已在题目描述中说明。

接下来的 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示编号为 $u$ 的点和编号为 $v$ 的点之间有一条边。

输出格式

输出 $n$ 行，每行一个整数。设所有不是 $i$ 的祖先也不是 $i$ 的后代的节点的权值构成的集合为 $S_i$，则第 $i$ 行的两个整数表示 $f(S_i)$。

数据范围

对于前 $20\%$ 的数据，$n \le 10^3$。

另有 $16\%$ 的数据，$n \le 2\times 10^4$，树高不超过 $25$。

另有 $16\%$ 的数据，存在两个不同的整数 $x$ 和 $y$，使得对于任意的 $1 \le i \le n$，$a_i = x$ 或 $a_i = y$ 成立。

对于 $100\%$ 的数据，$1 \le n \le 5\times10^4, \lvert a_i \rvert \le 10^9$。

6
7 5 -9 -3 2 4
1 2
1 3
2 4
2 5
3 6

-1
13
5
11
7
5

15
-999983193 -717524751 622650073 -15056342 144108930 -529788728 -898972456 457850878 458777923 -992762292 -176435560 115438165 784484492 -925756958 -885192013
1 2
3 2
2 4
2 5
6 3
4 7
8 3
8 9
10 3
11 8
10 12
2 13
8 14
1 15

-1
-1
870135671
355403285
355403285
708756453
355403285
640375562
640375562
355403285
514732386
355403285
355403285
355403285
353353168