有 $2n$ 个节点的树。每个节点拥有一个钥匙或一个锁。钥匙和锁各有 $n$ 种，编号为 $1$ 到 $n$。保证每种钥匙和每种锁均在树上刚好出现一次。

$cats$ 可以选择一个拥有钥匙的节点出发，沿着树的边移动任意多次。$cats$ 每次到达一个拥有钥匙的节点时（包括出发的节点），$cats$ 可以收集这个节点的钥匙。只有当 $cats$ 拥有编号为 $i$ 的钥匙时，$cats$ 才可以移动到拥有编号为 $i$ 的锁的节点。钥匙是不会被消耗的，也就是 $cats$ 在获得编号为 $i$ 的钥匙后，他可以移动到拥有编号为 $i$ 的锁的节点任意多次。

现在 $cats$ 想知道，对于每个拥有钥匙的节点，如果他选择这个节点作为出发的节点，他能否收集到全部的 $n$ 种钥匙。你能告诉 $cats$ 答案吗？

输入格式

第一行包含一个整数 $T$ $(1\leq T\leq 2\cdot 10^4)$，表示一共有 $T$ 组测试数据。

对于每组测试数据：

第一行为一个整数 $n$ $(1\leq n\leq 2\cdot 10^5)$，表示钥匙的总数和锁的总数。

第二行为 $2n$ 个整数 $a_1,a_2,\dots,a_{2n}$ $(−n\leq a_i\leq n, a_i\neq 0)$，表示每个节点拥有的钥匙或锁的编号。其中 $a_i>0$ 表示这个节点拥有编号为 $a_i$ 的钥匙，$a_i<0$ 表示这个节点拥有编号为 $-a_i$ 的锁。保证每种钥匙和每种锁均在树上刚好出现一次。

接下来 $2n−1$ 行，每行两个整数 $u_i,v_i$ $(1\leq u_i,v_i\leq 2n)$，表示一条连接节点 $u_i$ 和 $v_i$ 的边。保证这 $2n−1$ 条边构成一棵树。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个长度为 $n$ 的 $01$ 字符串。如果 $cats$ 从拥有编号为 $i$ 的钥匙的节点出发，可以收集到全部的 $n$ 种钥匙，则字符串中第 $i$ 个字符为 $1$。否则字符串中第 $i$ 个字符为 $0$。

样例

输入

4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6

输出

1
011
000
000