Binary Literature

给你一个正整数 $n$ 和三个长度为 $2\times n$ 的 01 字符串 $s_1,s_2,s_3$。你需要构造一个 01 字符串 $S$，使得： - 字符串 $S$ 的长度不能超过 $3\times n$。 - $s_1,s_2,s_3$ 当中至少有两个字符串是 $S$ 的子序列。 可以证明一定有解，有多种解时输出任意一种即可。$T$ 组数据。 $1\leq T\leq10^4;1\leq n,\sum n\leq10^5;$

A bitstring is a string that contains only the characters 0 and 1. Koyomi Kanou is working hard towards her dream of becoming a writer. To practice, she decided to participate in the Binary Novel Writing Contest. The writing prompt for the contest consists of three bitstrings of length $ 2n $ . A valid novel for the contest is a bitstring of length at most $ 3n $ that contains at least two of the three given strings as subsequences. Koyomi has just received the three prompt strings from the contest organizers. Help her write a valid novel for the contest. A string $ a $ is a subsequence of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero) characters.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ). Each of the following three lines contains a bitstring of length $ 2n $ . It is guaranteed that these three strings are pairwise distinct. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10^5 $ .

For each test case, print a single line containing a bitstring of length at most $ 3n $ that has at least two of the given bitstrings as subsequences. It can be proven that under the constraints of the problem, such a bitstring always exists. If there are multiple possible answers, you may output any of them.

2
1
00
11
01
3
011001
111010
010001

010
011001010

In the first test case, the bitstrings 00 and 01 are subsequences of the output string: 010 and 010. Note that 11 is not a subsequence of the output string, but this is not required. In the second test case all three input strings are subsequences of the output string: 011001010, 011001010 and 011001010.