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 '' and '') 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 and the second string is of length containing only '' and '', you have to find another binary string of length for Princess Rhaenyra, that the hamming distance between and is equal to the hamming distance between and , and string is a palindrome.
If this type of string is not available, then print . Otherwise, print . You can print any valid string C if there are multiple.
If the length of some string is denoted by , the Hamming Distance between two strings and of equal length is defined as , where is the character of string and is the character of string . For example, the Hamming distance between string and string is .
A Palindrome is a string that reads the same backward as forward. For example, strings "" , "" , "" , and "" are palindromes, but strings "", "", and "" are not.
The input starts with an integer ( ) denoting the number of test cases.
The first line of each test case contains one integer ( ) - the length of each string. The second and third lines contain two binary strings and (containing only '' and '') of length .
It's guaranteed that the sum of over all test cases does not exceed .
For each test case, print a binary string of length , which is a palindrome, and the hamming distance between and is equal to the hamming distance between and . If such a string is not possible, print .
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 which is a palindrome.
The hamming distance between and is and
hamming distance between and is .
In the second test case, there is no valid string.