← 返回题目列表

Codeforces · 1867/B

B. 异或回文

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$(仅由 $$$0$$$ 和 $$$1$$$ 组成的字符串)。如果存在长度为 $$$n$$$ 且包含 $$$x$$$ 的二进制字符串 $$$x$$$ ,则数字 $$$x$$$ 是好的,这样如果每个符号 $$$s_i$$$ 被替换为 $$$s_i \oplus l_i$$$ (其中 $$$\oplus$$$ 表示按位异或运算),那么字符串 $$$s$$$ 就成为回文。

您需要输出长度为 $$$n+1$$$ 的二进制字符串 $$$t$$$,其中 $$$t_i$$$ ($$$0 \leq i \leq n$$$) 等于 $$$1$$$ 如果数字 $$$i$$$ 是好的,否则 $$$0$$$ 。

回文是从左到右读取与从右到左读取相同的字符串。例如,01010、1111、0110 是回文。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一行,其中包含长度为 $$$n+1$$$ 的二进制字符串 $$$t$$$ - 问题的答案。

示例

输入 #1

5
6
101011
5
00000
9
100100011
3
100
1
1

输出 #1

0010100
111111
0011111100
0110
11

注意

考虑第一个例子。

- $$$t_2 = 1$$$ 因为我们可以选择 $$$l = $$$ 010100,那么字符串 $$$s$$$ 就变成了 111111,这是一个回文。
- $$$t_4 = 1$$$ 因为我们可以选择 $$$l = $$$ 101011。
- 可以证明,对于所有其他$$$i$$$,没有答案,因此剩下的符号是$$$0$$$。