In the discrete mathematics class, Serezha was told about binary Gray codes — is an ordering of all 2
n distinct binary vectors of length n such that any two adjacent vectors, as well as the first and last vectors, differ by exactly one bit.
To consolidate the material, the teacher gave them the following task: in the Gray code in each binary vector, exactly one bit is replaced by a question mark "?". It is required to replace back all the question marks "?" to "0" or "1" to get Gray code.
The teacher promised a bonus on the exam to the student who was the first to complete the task. Help Serezha to solve the problem or tell him that it is impossible and the teacher has given an unsolvable task.
Input data format
The first line contains an integer n — length of binary vectors. The next 2
n lines contain binary vectors of length n, each of which has exactly one character replaced with a question mark "?".
Output data format
In the first line print "YES" if the solution exists, and "NO" if it exists. — otherwise. If the answer is yes, print Gray's source code, if there are several possible answers, print any one.
|
Enter |
Output |
2
0?
0?
1?
1? |
YES
00
01
11
10 |
3
?00
0?1
01?
0?0
?10
1?1
10?
1?1
|
NO |
Grading system
|
Subtask number |
Points |
Restrictions |
Comments |
|
1 |
37 |
1<=n<=4 |
Points are awarded if all tests are passed. |
|
2 |
63 |
1<=n<=12 |
Points are awarded if all tests of this and previous subtasks are passed. |