What came first, the chicken or the egg?
Is it better to live a hundred years as a millionaire or seven days in poverty?
How to become a chess grandmaster?
How to raise blinds?
How to pass the final exams?
How to train a dragon?
These are interesting questions we can ponder only after the competition, but now we offer one less interesting computer science problem.
You are given two sets of numbers and of size . In one move, you can select an arbitrary element from set and change one arbitrary digit (bit) in its binary representation. The resulting number must not be an element of set immediately before the change.
For example, the number in binary is . In one move, it can become , , , or if we change its 4th, 3rd, 2nd, or 1st bit, respectively.
Determine a sequence of moves by which set becomes equal to set . Sets are equal if they have the same size and there is no element in set that does not belong to set .
Note: The number of moves does not have to be minimal, but it must satisfy the task constraints.
Input Specification
The first line contains the integer , the size of the sets and .
The second line contains distinct integers , the elements of the set .
The third line contains distinct integers , the elements of the set .
Output Specification
In the first line, print the number of required moves.
In the remaining lines, print the numbers and — we change the number from set to the number . The numbers and must differ by exactly one bit, and and must hold at the moment we execute the move.
The number of moves you make must not exceed . It can be shown that a solution always exists within the given constraints.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 10 | |
2 | 15 | |
3 | 30 | |
4 | 15 | No additional constraints. |
Sample Input 1
3
0 1 2
1 2 3
Sample Output 1
2
1 3
0 1
Explanation for Sample 1
If we first make the move 0 1
, and then 1 3
, between these two moves, set would have two identical elements, which the task does not allow.
A possible solution is 2 3
, 0 2
.
Sample Input 2
3
4 8 31
0 4 8
Sample Output 2
5
31 30
30 28
28 24
24 16
16 0
Explanation for Sample 2
. By removing bits from least to most significant, we obtain the numbers , , , , and in sequence. After all moves, set becomes equal to set .
Sample Input 3
5
0 1 2 4 5
7 6 5 3 2
Sample Output 3
9
1 3
3 7
0 1
1 0
2 6
0 2
7 3
5 7
4 5
Comments