嚣哥有全国最大的巧克力工厂，可是最近生产了太多巧克力金币，于是嚣哥决定用巧克力金币装饰工厂的圣诞树。 圣诞树的大小为 $ N $ ，共有 $ N $ 个节点与 $ N - 1 $ 条边，节点从 $ 1 $ 至 $ N $ 编号，其中节点 $ 1 $ 是树根，而圣诞树没有环和重边 。 嚣哥用了不同种类的巧克力金币装饰工厂的圣诞树，于节点 $ i $ 的巧克力金币种类为 $ c_i $ 。 为提高圣诞树的观赏性，嚣哥想知道圣诞树子树中最少的巧克力金币种类，注意最少的巧克力金币种类可多于一个。 比如圣诞树子树的巧克力金币种类为 $[1, 1, 2, 2, 2, 3, 3]$ ，最少的巧克力金币种类为 $1$ 和 $3$ 。 请你替嚣哥找出每一个节点的子树中，所有最少的巧克力金币种类的按位异或。

输入格式

第一行一个整数 $ N $，表示树的大小。
第二行 $ N $ 个整数 $ c_1, c_2, \cdots, c_N $，第 $i（1 \le i \le n ） $ 个整数表示节点 $ i $ 的巧克力金币种类。
接下来 $ N−1 $ 行每行两个整数 $ u,v $ ，表示一条连接 $ u $ 号节点与 $ v $ 号节点的边。

输出格式

输出一行共 $ N $ 个用空格隔开的整数，第 $ i $ 个数表示 $ i $ 号节点的子树中，所有最少的巧克力金币种类的按位异或。

数据范围

$1 \le N \le 10^5, 1 \le c_i \le N$
测试点 $1-4$：$N \le 1000$
测试点 $4-8$：树是一条链，即存在着一个 $[1\dots N]$ 的排列 $p$ 使得对于所有 $1 \le i \lt N, p_i$ 和 $p_{i+1}$ 有边。
测试点 $9-12$：树随机生成
测试点 $13-20$：没有其它限制