Araz 有一个长度为 $N$ 位的二进制序列，想要发送给 Baba。由于数据在传输过程中可能会损坏，他打算在源数据后面附加一个由 $K$ 位组成的序列，以便 Baba 在数据损坏的情况下能够恢复出原始的 $N$ 位数据。我们知道，在传输过程中，总共 $N + K$ 位数据中最多只有一位可能会损坏（即取反）。

你的任务是帮助 Araz 和 Baba 进行数据的发送和接收，同时使 $K$ 尽可能小。

实现细节

你应当实现以下两个不同的函数：

int[] get_attachment(int[] source)

• 此函数由 Araz 调用。
• source：一个长度为 $N$ 的整数数组，表示提供给 Araz 的二进制序列（所有整数均为 $0$ 或 $1$）。
• 该函数应返回一个由 $0$ 或 $1$ 组成的整数数组，其中包含附加到源序列末尾的 $K$ 位附加信息。该数组的长度不能超过 $2N$。

int[] retrieve(int[] data)

• 此函数由 Baba 调用。
• data：一个长度为 $N + K$ 的整数数组，表示 Baba 接收到的（可能已损坏的）数据序列（所有整数均为 $0$ 或 $1$）。
• 该函数必须返回一个长度为 $N$ 的整数数组，其中包含根据 Baba 接收到的数据恢复出的原始 $N$ 位序列。

考虑一个函数 manipulate，它接收一个二进制序列，并返回一个最多只有一位被取反的相似序列。你对 get_attachment 和 retrieve 的实现必须满足：对于任意长度为 $N$ 的二进制序列 source 以及任意函数 manipulate，都应当有 retrieve(manipulate(data)) = source，其中 data 是 source 和 get_attachment(source) 的拼接。否则，你的实现是错误的。

在一个测试点中包含 $T$ 个场景。对于每个场景，评测程序首先调用 get_attachment 函数并传入源序列。接着，它可能会将源序列或附加序列中的某一位取反。然后将结果传递给 retrieve 函数。请注意，在评测系统中，这些函数是在不同的程序中调用的。在第一个程序中，对每个场景调用一次 get_attachment 函数。对 retrieve 函数的调用是在第二个程序中进行的。你对每个场景的实现的运行行为必须独立于场景的顺序，因为在两个程序中场景的顺序可能不同。

子任务与评分

共有两个子任务：

• 子任务 1（60 分）：$N = 63$，$1 \le T \le 20\,000$
• 子任务 2（40 分）：$N = 255$，$1 \le T \le 200\,000$

如果在任何测试点的任何场景中恢复出的序列不正确，你在该子任务中的得分将为 $0$。否则，设 $Q$ 为该子任务所有测试点的所有场景中附加信息长度（$K$）的最大值。你的得分将按如下方式计算：

样例

假设 Araz 在源序列后附加了常数序列 $[0, 1, 0]$，而 Baba 直接忽略附加信息，仅将数据的前 $N$ 位作为源序列恢复。显然，这只是一个例子，并不是一个正确的策略。

评测程序进行以下函数调用：

get_attachment([0, 1, 1, 0, ..., 0, 0, 1])

在这个例子中，source 是 $[0, 1, 1, 0, ..., 0, 0, 1]$，函数返回 $[0, 1, 0]$。因此，要发送的完整数据为 $[0, 1, 1, 0, ..., 0, 0, 1, 0, 1, 0]$。

现在，假设在数据传输过程中，数据的最后一位损坏了。因此，评测程序进行以下函数调用：

retrieve([0, 1, 1, 0, ..., 0, 0, 1, 0, 1, 1])

该函数返回 $[0, 1, 1, 0, ..., 0, 0, 1]$，这恰好是正确的答案。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 $1$ 行：$T$
• 第 $2 + i$ 行（对于 $0 \le i \le T - 1$）：$c$ $source$
  • $c$：数据中损坏位的索引（从 $0$ 开始，$-1 \le c \le N + K - 1$）。如果 $c = -1$，则表示没有位损坏。
  • $source$：一个长度为 $N$ 的二进制（0/1）字符串，表示源序列。

样例评测程序按以下格式写入输出：

• 第 $1 + i$ 行（对于 $0 \le i \le T - 1$）：你的解决方案在场景 $i$ 中的判定结果。如果源序列被正确恢复，它还会输出 $K$。