三元数异或（秋季每日一题 4）

如果一个整数，其各个数位不包含 $0,1,2$ 以外的数字，则称这个数为三元数。

例如，$1022,11,21,2002$ 都是三元数。

给定一个可能很长的三元数 $x$，其首位数字（最左边那位）保证为 $2$，其他位数字为 $0$ 或 $1$ 或 2。

我们规定，两个长度为 $n$ 的三元数 $a$ 和 $b$ 可以通过三元异或运算 $\odot$ 得到另一个长度为 $n$ 的三元数 $c$。

设 $ai,bi,ci$ 分别表示 $a,b,c$ 的第 $i$ 位的数字，则 $ci=(ai+bi)mod3$。

例如，$10222\odot 11021=21210$。

你的任务是对于每个给定的 $x$，求出可以满足 $a\odot b=x$，并且 $max(a,b)$ 尽可能小的 $a,b$。

注意，$a,b$ 都必须是 $n$ 位三元数，且不含前导 $0$。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$，表示 $x$ 的长度。

第二行包含一个长度为 $n$，首位为 $2$ 的三元数 $x$。

输出格式
每组数据输出占两行，分别包含数 $a$ 和数 $b$。

如果答案不唯一，则输出任意合理答案均可。

数据范围
$1\le T\le 10^4,$
$1\le n\le 5\times 10^4,$
同一测试点所有 $n$ 的和不超过 $5\times 10^4$。

输入样例：

4
5
22222
5
21211
1
2
9
220222021
1
2
3
4
5
6
7
8
9

输出样例：

11111
11111
11000
10211
1
1
110111011
110111010
1
2
3
4
5
6
7
8

---

#include
#include

using namespace std;

const int N = 50010;

typedef long long LL;

int n;
char s[N], a[N], b[N];

int main(){
    
    int t;
    
    scanf("%d", &t);
    
    while(t--){
        
        scanf("%d%s", &n, s);
        
        char c1, c2;
        bool flag = false;
        for(int i = 0; i < n; i++){
            
            if(s[i] == '0'){
                
                c1 = c2 = '0';
                
            }else if(s[i] == '1'){
                
                if(flag) c1 = '1', c2 = '0';
                else flag = true, c1 = '0', c2 = '1';
                
            }else{
                
                if(i == 0 || !flag) c1 = c2 = '1';
                else c1 = '2', c2 = '0';
                
            }
            
            a[i] = c1, b[i] = c2;
        }
        a[n] = '\0', b[n] = '\0';
        puts(a), puts(b);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50