/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
3 つの 01 文字列 S_1, S_2, S_3 が与えられます。これらはそれぞれ、0 と 1 を N 個ずつ含みます。
長さ 2N+1 の 01 文字列であって、S_1 + S_1, S_2 + S_2, S_3 + S_3 のいずれの部分列でもあるものを 1 つ求めてください（s+t は文字列 s, t をこの順に連結したものを表します）。この問題の制約の下では、そのような文字列が常に存在することが保証されます。
ここで、文字列 B が文字列 A の部分列であるとは、A から 0 文字以上を取り除き、残りの文字を順番を変えずに連結することで B を得ることができることを意味します。
テストケースは T 個与えられるので、それぞれを解いてください。
制約
- 1 \le T \le 10^5
- 1\le N \le 10^5
- S_i は
0と1を N 個ずつ含む 01 文字列である。 - 全テストケースにおける N の総和は 10^5 以下である。
入力
入力は以下の形式で標準入力から与えられる。 入力の 1 行目は次の通りである。
T
そして、それぞれ以下の形式で T 個のテストケースが続く。
N S_1 S_2 S_3
出力
各テストケースについて、長さ 2N+1 の 01 文字列であって、S_1 + S_1, S_2 + S_2, S_3 + S_3 のいずれの部分列でもあるようなものをいずれか 1 つ出力せよ。 そのような文字列が複数存在するときは、いずれを出力してもよい。
入力例 1
2 1 01 01 10 2 0101 0011 1100
出力例 1
010 11011
1 個目のケースでは、010 は 0101, 0101, 1010 の部分列です。
2 個目のケースでは、11011 は 01010101, 00110011, 11001100 の部分列です。
Score : 400 points
Problem Statement
You are given 3 binary strings S_1, S_2, S_3, each containing exactly N 0's and N 1's.
Find a binary string of length 2N+1, which is a subsequence of all of the strings S_1 + S_1, S_2 + S_2, S_3 + S_3 (s+t denotes the concatenation of strings s and t in order). It's guaranteed that under the constraints above such a string always exists.
Here a string B is a subsequence of a string A if B can be obtained by removing zero or more characters from A and concatenating the remaining characters without changing the order.
You will be given T test cases. Solve each of them.
Constraints
- 1 \le T \le 10^5
- 1\le N \le 10^5
- S_i is a binary string of length 2N consisting of N
0's and N1's. - The sum of N over all test cases doesn't exceed 10^5.
Input
Input is given from Standard Input in the following format. The first line of input is as follows:
T
Then, T test cases follow, each of which is in the following format:
N S_1 S_2 S_3
Output
For each test case, print any binary string of length 2N+1, which is a subsequence of all of S_1 + S_1, S_2 + S_2, S_3 + S_3. If many such strings exist, you can print any.
Sample Input 1
2 1 01 01 10 2 0101 0011 1100
Sample Output 1
010 11011
In the first case, 010 is a subsequence of 0101, 0101, and 1010.
In the second case, 11011 is a subsequence of 01010101, 00110011, and 11001100.