C. -is-this-bitset-
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note the low memory limit!

You are given a binary tree with $$$n$$$ nodes in it, rooted at node $$$1$$$. This means that each node has at most $$$2$$$ children. You are also given two arrays of $$$n$$$ integers, $$$a$$$ and $$$b$$$

The subset problem for node $$$i$$$ is defined to be the question: Can you take a subset $$$S$$$ of the ancestors of node $$$i$$$ and itself, such that $$$\sum_{j \in S} (a_j) = b_i$$$

You can do at most $$$5000$$$ operations on array $$$a$$$. In one operation you choose two integers $$$i$$$ and $$$x$$$ ($$$ 1 \leq i \leq n$$$, $$$0 \leq x \leq 2 \cdot 10^6$$$), and set $$$a_i := x$$$.

After these operations, solve the subset sum problem for each node $$$i$$$, and output the results as a bitstring.

Input

The first line contains the integer $$$n$$$ ($$$1 \leq n \leq 300\,000$$$)  — the size of the binary tree The next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \neq v$$$)  — nodes $$$u$$$ and $$$v$$$ are connected by an edge.

It is guaranteed that these edges form a binary tree rooted at node $$$1$$$

The next line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^6$$$)  — the array $$$a$$$.

The last line of the input contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ ($$$0 \leq b_i \leq 2 \cdot 10^6$$$)  — the array $$$b$$$

Output

Output $$$n$$$ integers $$$a^\prime_1, a^\prime_2, \dots, a^\prime_n$$$ ($$$0 \leq a^\prime_i \leq 2 \cdot 10^6$$$)  — the new array $$$a^\prime$$$, which is the array $$$a$$$ after the operations were done on it.

On the next line, output a bitstring of length $$$n$$$, with a $$$1$$$ on position $$$i$$$, if the subset problem on node $$$i$$$ can be solved, and $$$0$$$ otherwise.

Examples
Input
5
2 1
1 3
3 4
5 4
1 3 11 12 6
0 5 12 13 18
Output
1 3 11 12 0
10110
Input
1
2000000
2000000
Output
2000000
1
Note

In the sample output, it was decided to change the last number of array $$$a$$$ into $$$0$$$.