请注意内存限制！

给定一棵包含 $n$ 个节点的二叉树，根节点为 1。这意味着每个节点最多有两个子节点。同时给定两个包含 $n$ 个整数的数组 $a$ 和 $b$。

对于节点 $i$，子集和问题定义为：能否从节点 $i$ 的祖先（包含节点 $i$ 本身）中选取一个子集 $S$，使得 $\sum_{j \in S} a_j = b_i$。

你可以对数组 $a$ 进行最多 5000 次操作。每次操作中，你可以选择两个整数 $i$ 和 $x$（$1 \le i \le n$，$0 \le x \le 2 \cdot 10^6$），并将 $a_i$ 修改为 $x$。

在进行这些操作后，请解决每个节点 $i$ 的子集和问题，并以位串形式输出结果。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 300\,000$）——二叉树的大小。接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n, u \neq v$）——表示节点 $u$ 和 $v$ 之间有一条边。 保证这些边构成一棵以节点 1 为根的二叉树。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2 \cdot 10^6$）——数组 $a$。 最后一行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 2 \cdot 10^6$）——数组 $b$。

输出格式

输出 $n$ 个整数 $a'_1, a'_2, \dots, a'_n$（$0 \le a'_i \le 2 \cdot 10^6$）——即操作完成后的新数组 $a'$。 在下一行，输出一个长度为 $n$ 的位串。如果节点 $i$ 的子集和问题有解，则第 $i$ 位为 1，否则为 0。

样例

样例输入 1

5
2 1
1 3
3 4
5 4
1 3 11 12 6
0 5 12 13 18

样例输出 1

1 3 11 12 0
10110

样例输入 2

1
2000000
2000000

样例输出 2

2000000
1

说明

在样例输出中，我们将数组 $a$ 的最后一个数字修改为了 0。