← 返回题目列表

Codeforces · 1328/C

C. 三元异或

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

如果一个数字仅包含数字 $$$0$$$、$$$1$$$ 和 $$$2$$$,则该数字是三进制的。例如,以下数字是三元:$$$1022$$$、$$$11$$$、$$$21$$$、$$$2002$$$。

给你一个长三进制数$$$x$$$。 $$$x$$$ 的第一个(最左边)数字保证为 $$$2$$$,$$$x$$$ 的其他数字可以是 $$$0$$$、$$$1$$$ 或 $$$2$$$。

让我们将两个三元数 $$$a$$$ 和 $$$b$$$(长度均为 $$$n$$$)的三元异或运算 $$$\odot$$$ 定义为数字 $$$c = a \odot b$$$,长度为 $$$n$$$,其中 $$$c_i = (a_i + b_i) \% 3$$$ (其中$$$\%$$$ 是模运算)。换句话说,将相应的数字相加,然后除以 $$$3$$$ 求余数。例如,$$$10222 \odot 11021 = 21210$$$。

你的任务是找到这样的三元数 $$$a$$$ 和 $$$b$$$ ,两者的长度都是 $$$n$$$ 并且都没有前导零,使得 $$$a \odot b = x$$$ 和 $$$max(a, b)$$$ 是可能的最小值。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — $$$x$$$ 的长度。测试用例的第二行包含三进制数 $$$x$$$,由 $$$n$$$ 数字 $$$0、1$$$ 或 $$$2$$$ 组成。保证 $$$x$$$ 的第一位数字是 $$$2$$$。保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^4$$$ ($$$\sum n \le 5 \cdot 10^4$$$)。

输出

对于每个测试用例,打印答案 - 两个三元整数 $$$a$$$ 和 $$$b$$$ 长度均为 $$$n$$$ 并且都没有前导零,使得 $$$a \odot b = x$$$ 和 $$$max(a, b)$$$ 是可能的最小值。如果有多个答案,您可以打印任何一个。

示例

输入 #1

4
5
22222
5
21211
1
2
9
220222021

输出 #1

11111
11111
11000
10211
1
1
110111011
110111010