描述

在当代 VLSI 芯片行业，电气工程师使用的软件工具执行多种优化。您的任务是实现某些芯片设计的特定优化。您的工具给定了一个无环的 NAND 门网络（NAND 门计算其输入的否定结合，即当且仅当其两个输入值均为 $1$ 时，门的输出值为 $0$ ）。该网络是已经合成的组件的一部分，无法更改。网络的所有输入都连接到一个信号 $x$。目标是断开 $x$ 与一些输入的连接，并为这些输入分配常量信号 $0$ 和/或 $1$，以便以这样的方式实现的功能与所有输入都连接到 $x$ 时相同。我们称将 $x$ 或 $0$ 或 $1$ 分配给网络输入的分配为最优分配，如果连接到 $x$ 的输入数量尽可能少，但网络仍然计算相同的功能，就好像所有输入都连接到 $x$。

请查看以下设计。

我们可以将其更改为仅一个变量输入的设计，例如：

（请注意，还有其他方法将输入连接到仅一个 $x$ 和一些 $0$ 和 $1$，以实现相同的功能）。

编写一个程序，对于每个数据集：

• 读取网络的描述，

• 计算对网络输入的 $x$ 或 $0$ 或 1 的最优分配，

• 输出结果。

输入

输入的第一行包含一个正整数 $d$ ，表示数据集的数量，$1 ≤ d ≤ 20$。数据集随之而来。

每个数据集由两行连续的行组成。第一行包含两个正整数 $n$ 和 $m$，以空格分隔，$1 ≤ n ≤ 100000$ ，$1 ≤ m ≤ 200000$。整数 $n$ 是网络输入的数量，整数 $m$ 是网络中门的数量。

第二行包含恰好 $2m$ 个非零整数，以空格分隔。位置 $2j − 1$ 和 $2j$ 上的数字表示第 $j$ 个门的输入信号源。正数 $s$ 表示门 $s$ 的输出。负数 $s$ 表示第 $(−s)$ 个网络输入。门的输入连接到网络的输入或早期序列中出现的门的输出。每个网络输入至少连接到一个门输入。每个门的输出至少连接到一个门输入，除了最后一个门的输出，该门连接到网络的输出。

输出

输出应由恰好 $d$ 行组成，每行包含一组结果。第 $i$ 行应包含第 $i$ 个数据集的答案。

对于一个数据集的答案应由恰好 $k$ 个字符组成，以换行符结束（没有空格）。该序列的第 $i$ 个符号表示分配给第 $i$ 个网络输入的值，可以是 $‘0’$（数字 ‘零’）$‘1’$（数字 ‘一’）或 $‘x’$（小写字母 $‘x’$）。

如果有多个最优分配，则您的程序可以输出其中任何一个（但仅限于一个）。