Limits
1s, 512 MB

Today Queen Alicent Hightower, came to King Viserys Targaryen with a gift box. Viserys was so happy to see those gifts. After opening the gift box, he found two binary strings (containing only '$0$' and '$1$') of same length.

To test the problem-solving ability of his dearest daughter, Princess Rhaenyra Targaryen, he asked Rhaenyra to find a string such that the string is a palindrome and the hamming distance between Rhaenyra's string and Queen Alicent's first string is equal to the hamming distance between Rhaenyra's string and Alicent's second string. Rhaenyra is not so good at programming. Rhaenyra asks for your help to solve the problem. Can you help her?

More formally, If Alicent’s first string is $A$ and the second string is $B$ of length $n$ containing only '$0$' and '$1$', you have to find another binary string $C$ of length $n$ for Princess Rhaenyra, that the hamming distance between $C$ and $A$ is equal to the hamming distance between $C$ and $B$, and string $C$ is a palindrome.

If this type of string $C$ is not available, then print $-1$. Otherwise, print $C$. You can print any valid string C if there are multiple.

If the length of some string $s$ is denoted by $|s|$, the **Hamming Distance** between two strings $s$ and $t$ of equal length is defined as $\sum\limits_{i=1}^{|s|} |s_i - t_i|$, where $s_i$ is the $i^{th}$ character of string $s$ and is the $i^{th}$character of string $t$. For example, the Hamming distance between string $0011$ and string $0110$ is $|0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2$.

A **Palindrome** is a string that reads the same backward as forward. For example, strings "$1$" , "$000$" , "$010$" , and "$101101$" are palindromes, but strings "$10$", "$0010$", and "$110$" are not.

The input starts with an integer $T$($1$ $\leq$ $T$ $\leq$ $10^5$) denoting the number of test cases.

The first line of each test case contains one integer $n$ ( $1$ $\leq$ $n$ $\leq$ $10^5$) - the length of each string. The second and third lines contain two binary strings $A$ and $B$ (containing only '$0$' and '$1$') of length $n$.

It's guaranteed that the sum of $n$ over all test cases does not exceed $2⋅10^5$.

For each test case, print a binary string $C$ of length $n$, which is a palindrome, and the hamming distance between $C$ and $A$ is equal to the hamming distance between $C$ and $B$. If such a string is not possible, print $-1$.

If multiple valid strings are possible, print any of them.

Input | Output |
---|---|

2 6 001100 111111 1 1 0 | 010010 -1 |

In the first test case, a valid string can be $010010$ which is a palindrome.

The hamming distance between $010010$ and $001100$ is $|0-0|+|1-0|+|0-1|+|0-1|+|1-0|+|0-0| = 4$ and

hamming distance between $010010$ and $111111$ is $|0-1|+|1-1|+|0-1|+|0-1|+|1-1|+|0-1| = 4$.

In the second test case, there is no valid string.

Toph uses cookies. By continuing you agree to our Cookie Policy.