Ana 有 $N$ 对自然数，其取值范围在 $1$ 到 $10^9$ 之间。另外，不存在两个对拥有相同的第一个数。因此，我们可以将 Ana 的这些数对看作是一个映射（例如 C++ 中的 map<int,int>）。 数对中的第一个数称为键，第二个数称为值。

Ana 想要将她的映射内容发送给 Borna，但她所使用的通信信道允许传输的比特数是有限的！因此，Ana 必须设计一种方法，将她的映射转换成一个指定长度的比特序列，并通过通信信道发送给 Borna。

Borna 会接收到这个比特序列，并尝试从中重建 Ana 的映射。即使他可能无法得知整个映射的内容，他也必须能够实现映射的功能。更准确地说，对于任意属于键集合的值 $x$，Borna 必须能够返回映射中对应的值 $map[x]$。为了确认是否成功重建了映射，Borna 将会询问某些键值共 $Q$ 次。

请帮助 Ana 和 Borna，编写一个程序，将给定的映射转换为比特序列，并能够从给定的比特序列中重建原始映射。

输入格式

第一行是自然数 $T$（$T = 1$ 或 $T = 2$）。

• 如果 $T = 1$，程序必须将给定的映射编码为一个比特序列。
• 如果 $T = 2$，程序必须从给定的比特序列中重建原始映射。

如果 $T = 1$： 下一行是自然数 $N$（$1 \le N \le 100$），表示 Ana 的映射中数对的数量。接下来的 $N$ 行中，第 $i$ 行包含自然数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le 10^9$），分别表示映射中一个数对的键和值。保证当 $i \ne j$ 时，$x_i \ne x_j$。

如果 $T = 2$：下一行包含三个自然数 $N$、$Q$ 和 $K$（$1 \le N, Q \le 100$，$1 \le K \le 6000$），分别表示映射中的数对数量、Borna 提出的查询次数以及接收到的比特数量。下一行是一个长度为 $K$ 的字符串，仅由字符 0 和 1 组成，表示接收到的比特序列。接下来的 $Q$ 行中，第 $i$ 行包含一个自然数 $x_i$。保证 $x_i$ 一定属于原始映射的键集合。

输出格式

如果 $T = 1$： 第一行输出自然数 $K$（$1 \le K \le 6000$），表示编码后的比特序列长度。第二行输出一个由字符 0 和 1 组成的字符串，表示发送的比特序列。

如果 $T = 2$： 输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

子任务

你的解法将分两个步骤进行测试。首先，程序会在 $T = 1$ 的官方输入数据上运行。如果输出是一个合法的长度为 $K$ 的比特序列，则在第二步中，程序会再次运行，并使用第一步输出的比特序列作为输入。如果第二步中程序对查询给出的答案与官方输入中的映射一致，则认为程序成功重建了映射。

如果程序未能成功重建映射，则得分为 0 分。否则，得分取决于 $K$，规则如下表所示：

程序的运行时间为两个评测步骤运行时间之和。

样例数据

交互示例

输入

1
3
2 10
3 3
5 7

输出

7
1100111

输入

2
3 2 7
1100111
5
3

输出

7
3