题目背景

题目来源：link。

题目描述

有一棵树，叫逻辑树。

这个树有根，有 $2N-1$ 个节点，其中 $N$ 个叶子，每个非叶节点恰好有两个孩子。

每个叶子上有一个 01 变量，它的取值可能为 True 或 False。每个非叶节点上有一个逻辑运算符，这个运算可能为 AND 或者 OR。

一个非叶节点的取值定义为它两个儿子的取值，作这个节点上的运算得到的结果。

有一个黑恶势力想知道这个树的根节点的取值，他准备了一个长度为 $N$ 的询问序列 $\{P_i\}$，每个叶子在这个序列中恰好出现一次。

黑恶势力会依次询问这些叶子的值，但是，如果他发现某一次询问是不必要的，那么他会跳过这个无意义的询问（为了帮助理解，考虑 x AND y 在我们知道 x 为 False 之后，不必知道 y 的值就可推算 x AND y 的值）。

当然，邪恶总是能战胜正义，黑恶势力总能达到他的目的。但是我们可以拖慢他的节奏，你现在可以安排每个叶子的权值，使得黑恶势力询问的次数尽可能多，在此基础上，我们希望这个树的根节点取值尽量为 True。

请你计算一组解，任何一种合法方案都是可以接受的。

输入格式

第一行一个整数 $N$，意义如题面所示。

接下来一行 $N-1$ 个整数，第 $i$ 个数代表节点 $N+i$ 上的运算符，其中 $0$ 表示 AND，$1$ 表示 OR。

接下来 $2N-2$ 行，每行两个整数，描述一条边。

最后一行 $N$ 个整数，表示黑恶势力的询问序列。

你可以认为 $1\sim N$ 是叶子，$N+1\sim 2N-1$ 是非叶节点，且 $N+1$ 是根，输入数据保证每个非叶节点有两个孩子。

输出格式

输出一个长度为 $N$ 的 01串 $S$，其中 $S_i$ 表示第 $i$ 个叶子的取值，$0$ 为 False, $1$ 为 True.

4
0 1 0
5 6
5 7
6 1
6 2
7 3
7 4
4 2 3 1

1011

提示

数据范围：

$\def\arraystretch{1.21} \begin{array}{|c|c|c|}\hline \bold{\small{子任务}}&\textbf{score}&\textbf{constraints}\\\hline \text{A}&40&\small{树的高度不超过 50}\\\hline \text{B}&60&\small{无特殊限制}\\\hline \end{array}$

对于所有数据，$N\le 5\times 10^5$。

对于所有数据，保证 $1\le m<n\le1000$，$1\le k\le10000$，$1\le p_i\le n,1\le x_i\le m$，$p_i$ 互不相等。