Contest Duration: - (local time) (160 minutes) Back to Home
A - Long Common Subsequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

3 つの 01 文字列 S_1, S_2, S_3 が与えられます。これらはそれぞれ、01N 個ずつ含みます。

ここで、文字列 B が文字列 A の部分列であるとは、A から 0 文字以上を取り除き、残りの文字を順番を変えずに連結することで B を得ることができることを意味します。

テストケースは T 個与えられるので、それぞれを解いてください。

### 制約

• 1 \le T \le 10^5
• 1\le N \le 10^5
• S_i01N 個ずつ含む 01 文字列である。
• 全テストケースにおける N の総和は 10^5 以下である。

### 入力

T


そして、それぞれ以下の形式で T 個のテストケースが続く。

N
S_1
S_2
S_3


### 入力例 1

2
1
01
01
10
2
0101
0011
1100


### 出力例 1

010
11011


1 個目のケースでは、0100101, 0101, 1010 の部分列です。

2 個目のケースでは、1101101010101, 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 N 1'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.