Cyberland Circuit Foundation 由 $n$ 名成员组成。每名成员都有一个喜爱的数字和一个唯一的名字（喜爱的数字不一定互不相同）。
成员之间发送了 $m$ 封信。每封信都有一个发送者和一个接收者，信的内容是发送者喜爱的数字。
每名成员计算他们收到的信件内容（发送者喜爱的数字）之和，并对 $65536$（即 $2^{16}$）取模，作为他/她的结果数字。
你的任务是确定所有成员的结果数字。
然而，情况并不像看起来那么简单。Alice、Bob 和 Circuit 决定以一种稍微复杂的方式解决这个问题：
- Alice 知道所有 $n$ 名成员（名字和喜爱的数字），但对信件一无所知。她需要向 Circuit 发送一个长度不超过 $10^5$ 的二进制字符串。
- Bob 知道所有 $m$ 封信（发送者和接收者的名字），但对成员信息一无所知。他需要向 Circuit 发送一个长度不超过 $10^5$ 的二进制字符串。
- Circuit 可以接收 Alice 和 Bob 发送的二进制字符串，并随后生成一个包含 $16n$ 位的二进制字符串作为输出。然而，由于其计算能力有限，Circuit 只能执行基本的逻辑运算（例如 AND、OR、NOT）。
下面我们将详细介绍电路的工作原理。
电路细节
门是电路的基本元件。一个门由零个或两个布尔输入（取决于门的类型）和一个布尔输出组成。门有两种类型：输入门和计算门。
输入门没有输入，代表 Alice 和 Bob 发送的二进制字符串中的位。 将会有 $l_A + l_B$ 个输入门，编号从 $0$ 到 $(l_A + l_B - 1)$，其中 $l_A, l_B$ 分别是 Alice 和 Bob 发送的字符串长度。
- 对于 $0 \le i < l_A$，第 $i$ 个门的输出是 Alice 发送字符串的第 $i$ 位；
- 对于 $0 \le i < l_B$，第 $(i + l_A)$ 个门的输出是 Bob 发送字符串的第 $i$ 位。
计算门有两个输入，代表计算过程。 计算门的编号从 $(l_A + l_B)$ 开始。
- 对于每个计算门，你需要提供两个相关门的编号作为输入，以及操作类型 $p(0 \le p \le 15)$。
- 为了防止循环依赖，两个相关门的编号必须小于该计算门的编号。
- 如果其两个相关门的输出分别为 $x_0$ 和 $x_1$（$x_0, x_1 \in \{0, 1\}$），则计算门的输出为： $$f(p, x_0, x_1) = \left\lfloor \frac{p}{2^{x_0 + 2x_1}} \right\rfloor \pmod 2$$
以下是一些可能有用的示例：
| $x_0$ | $x_1$ | $x_0 \text{ AND } x_1$ $f(8, x_0, x_1)$ |
$x_0 \text{ OR } x_1$ $f(14, x_0, x_1)$ |
$x_0 \text{ XOR } x_1$ $f(6, x_0, x_1)$ |
$\text{NOT } x_0$ $f(5, x_0, x_1)$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
实现细节
请注意：
- 所有数组下标从 $0$ 开始。例如，如果 $a$ 是一个长度为 $n$ 的数组，则 $a[0]$ 到 $a[n-1]$ 是有效数据，访问超出该范围的下标可能会导致越界错误。
- 所有字符串均以空字符
\0结尾。
你需要实现以下过程：
Alice
int alice(const int n, const char names[][5],
const unsigned short numbers[], bool outputs_alice[]);| 方向 | 值 | 长度 | 含义 | 约束 |
|---|---|---|---|---|
| 输入 | $n$ | $1$ | $n$ | $0 \le n \le 700$ |
| 输入 | names |
$n$ | 每个成员的名字。 | 所有名字互不相同，仅由小写英文字母组成，最大长度为 4 个字符。 |
| 输入 | numbers |
$n$ | 每个成员喜爱的数字。 | 每个数字在 $0$ 到 $65535$ 之间。 |
| 输出 | outputs_alice |
$l_A$ | 发送给 Circuit 的二进制字符串。 | |
| 输出 | (返回值) | $1$ | $l_A$ | 你需要确保 $l_A$ 不超过 $10^5$，且当 $n$ 相同时，$l_A$ 必须固定。 |
Bob
int bob(const int m, const char senders[][5],
const char recipients[][5], bool outputs_bob[]);| 方向 | 值 | 长度 | 含义 | 约束 |
|---|---|---|---|---|
| 输入 | $m$ | $1$ | $m$ | $0 \le m \le 1000$ |
| 输入 | senders |
$m$ | 每封信的发送者名字。 | 所有名字均出现在 Alice 的输入中。 |
| 输入 | recipients |
$m$ | 每封信的接收者名字。 | |
| 输出 | outputs_bob |
$l_B$ | 发送给 Circuit 的二进制字符串。 | |
| 输出 | (返回值) | $1$ | $l_B$ | 你需要确保 $l_B$ 不超过 $10^5$，且当 $m$ 相同时，$l_B$ 必须固定。 |
Circuit
为了确保 Circuit 的计算过程类似于通用电路，你不能直接获取 Alice 和 Bob 发送给 Circuit 的二进制字符串。你只知道这两个字符串的长度并输出电路结构。
int circuit(const int la, const int lb, int operations[],
int operands[][2], int outputs_circuit[][16]);| 方向 | 值 | 长度 | 含义 | 约束 |
|---|---|---|---|---|
| 输入 | la |
$1$ | $l_A$ | |
| 输入 | lb |
$1$ | $l_B$ | |
| 输出 | operations |
$l$ | 电路中每个门执行的操作类型。 | $0$ 到 $15$ 之间的整数。 |
| 输出 | operands |
$l$ | 电路中每个门使用的操作数。 | 该数字必须小于当前门的编号。 |
| 输出 | outputs_circuit |
$n$ | 电路输出的门编号。 | outputs_circuit[i][j] 表示第 $i$ 名成员最终结果的第 $j$ 位（从最低有效位开始计数）。成员按 Alice 的输入顺序排列。 |
| 输出 | (返回值) | $1$ | $l$，表示总门数（包括输入门）。 | 你需要确保 $l \le 2 \times 10^7$ |
虽然你可以修改 operations 和 operands 数组中索引小于 $l_A + l_B$ 的门的信息，但评测程序会忽略此类修改。
数据范围
对于所有测试用例：
- $0 \le n \le 700, 0 \le m \le 1000$。
- 所有名字互不相同，仅由小写英文字母组成，最大长度为 4 个字符。
- 每名成员喜爱的数字在 $0$ 到 $65535$ 之间。
- 所有发送者和接收者的名字均出现在 Alice 的输入数组
names中。 alice()和bob()的内存限制为 $2048 \text{ MiB}$，时间限制分别为 $0.02$ 秒。circuit()的内存限制为 $2048 \text{ MiB}$，时间限制为 $7$ 秒。
在最终评估中，alice() 和 bob() 在单个测试用例中可能会被多次调用。$0.02$ 秒的时间限制适用于每次调用。
子任务
子任务 A（12 分）
子任务 1, 2, 3 属于子任务类型 A，其中 $n = 1$。 每个子任务具有以下附加约束： 子任务 1（4 分）：$m = 0$。 子任务 2（4 分）：$0 \le m \le 1$。 * 子任务 3（4 分）：$0 \le m \le 1000$。
子任务 B（54 分）
子任务 4, 5, 6 属于子任务类型 B，其中：
$0 \le n \le 30, \frac{n}{2} \le m \le n^2$。
不存在两封信的发送者和接收者完全相同。
所有成员的名字都出现在 Bob 的输入中（即每名成员要么至少发送一封信，要么至少收到一封信）。
每个子任务具有以下附加约束：
子任务 4（24 分）：$n = 26$，所有成员的名字均为单个小写字母，且在 Alice 的输入中按从 a 到 z 的顺序出现。
子任务 5（24 分）：$n = 26$。
* 子任务 6（6 分）：无特殊限制。
子任务 C（34 分）
子任务 7, 8, 9 属于子任务类型 C，其中 $0 \le n \le 700, 0 \le m \le 1000$。
每个子任务具有以下附加约束：
子任务 7（18 分）：$n = 676$，所有成员的名字均为两个小写字母，且在 Alice 的输入中按字典序出现（例如 aa, ab, ac, ..., az, ba, ..., bz, ca, ..., zz）。
子任务 8（10 分）：$n = 676$。
* 子任务 9（6 分）：无附加约束。
样例
样例评测程序按以下格式读取输入：
第 1 行：$n \ m$
第 $2 + i$ 行（$0 \le i \le n - 1$）：names numbers
* 第 $2 + n + i$ 行（$0 \le i \le m - 1$）：senders recipients
样例评测程序按以下格式输出：
如果程序成功完成，样例评测程序将输出 $n$ 行，每行包含一个整数，表示你为每名成员实现的函数所计算出的最终结果。
否则，评测程序将不会向标准输出输出任何内容，并将错误信息打印到目录下的 abc.log 文件中。
* 此外，样例评测程序会将 $l_A, l_B, l$ 的值以及每个函数的运行时间输出到 abc.log。
样例评测程序不会检查内存限制，也不会检查“对于相同的 $n/m$，$l_A/l_B$ 必须相等”这一限制。