#agc052a. [agc052_a]Long Common Subsequence

[agc052_a]Long Common Subsequence

问题陈述

给定 33 个二进制字符串 S1,S2,S3S_1, S_2, S_3,每个字符串都包含 NN0NN1

找到一个长度为 2N+12N+1 的二进制字符串,它是字符串 S1+S1,S2+S2,S3+S3S_1 + S_1, S_2 + S_2, S_3 + S_3 的子序列(s+ts+t 表示以顺序连接字符串 sstt)。保证在上述约束条件下,这样的字符串总是存在。

对于一个字符串 BB,如果可以通过从字符串 AA 中删除零个或多个字符,并连接剩余的字符而不改变顺序,得到字符串 BB,那么字符串 BB 是字符串 AA 的子序列。

你将获得 TT 个测试用例。解决每个测试用例。

约束条件

  • 1leTle1051 \\le T \\le 10^5
  • 1leNle1051\\le N \\le 10^5
  • SiS_i 是一个长度为 2N2N 的二进制字符串,由 NN0NN1 组成。
  • 所有测试用例中 NN 的总和不超过 10510^5

输入

输入格式如下,从标准输入给出。输入的第一行如下所示:

TT

然后,跟随 TT 个测试用例,每个测试用例的格式如下:

NN S1S_1 S2S_2 S3S_3

输出

对于每个测试用例,打印任何长度为 2N+12N+1 的二进制字符串,它是 S1+S1,S2+S2,S3+S3S_1 + S_1, S_2 + S_2, S_3 + S_3 的子序列。如果存在多个这样的字符串,你可以打印任意一个。

示例输入 1

2
1
01
01
10
2
0101
0011
1100

示例输出 1

010
11011

在第一个案例中,010010101011010 的子序列。

在第二个案例中,11011010101010011001111001100 的子序列。