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 '00' and '11') 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 AA and the second string is BB of length nn containing only '00' and '11', you have to find another binary string CC of length nn for Princess Rhaenyra, that the hamming distance between CC and AA is equal to the hamming distance between CC and BB, and string CC is a palindrome.

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

If the length of some string ss is denoted by s|s|, the Hamming Distance between two strings ss and tt of equal length is defined as i=1ssiti\sum\limits_{i=1}^{|s|} |s_i - t_i|, where sis_i is the ithi^{th} character of string ss and is the ithi^{th}character of string tt. For example, the Hamming distance between string 00110011 and string 01100110 is 00+01+11+10=0+1+0+1=2|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 "11" , "000000" , "010010" , and "101101101101" are palindromes, but strings "1010", "00100010", and "110110" are not.

Input

The input starts with an integer TT(11 \leq TT \leq 10510^5) denoting the number of test cases.

The first line of each test case contains one integer nn ( 11 \leq nn \leq 10510^5) - the length of each string. The second and third lines contain two binary strings AA and BB (containing only '00' and '11') of length nn.

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

Output

For each test case, print a binary string CC of length nn, which is a palindrome, and the hamming distance between CC and AA is equal to the hamming distance between CC and BB. If such a string is not possible, print 1-1.

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

Sample

InputOutput
2
6
001100
111111
1
1
0
010010
-1

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

The hamming distance between 010010010010 and 001100001100 is 00+10+01+01+10+00=4|0-0|+|1-0|+|0-1|+|0-1|+|1-0|+|0-0| = 4 and

hamming distance between 010010010010 and 111111111111 is 01+11+01+01+11+01=4|0-1|+|1-1|+|0-1|+|0-1|+|1-1|+|0-1| = 4.

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

Submit

Login to submit.

Statistics

50% Solution Ratio
utshabEarliest, Nov '22
HilariaFastest, 0.0s
Kuddus.6068Lightest, 4.9 MB
HilariaShortest, 1388B
Toph uses cookies. By continuing you agree to our Cookie Policy.