31684번 - Bitovi 서브태스크스페셜 저지다국어

문제

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 $A$ and $B$ of size $N$. In one move, you can select an arbitrary element from set $A$ and change one arbitrary digit (bit) in its binary representation. The resulting number must not be an element of set $A$ immediately before the change.

For example, the number 5ドル$ in binary is 0101ドル_2$. In one move, it can become 13ドル = 1101_2,ドル 1ドル = 0001_2,ドル 7ドル = 0111_2,ドル or 4ドル = 0100_2$ if we change its 4ドル$th, 3ドル$rd, 2ドル$nd, or 1ドル$st bit, respectively.

Determine a sequence of moves by which set $A$ becomes equal to set $B$. Sets are equal if they have the same size and there is no element in set $A$ that does not belong to set $B$.

Note: The number of moves does not have to be minimal, but it must satisfy the task constraints.

입력

The first line contains the integer $N$ (1ドル ≤ N ≤ 2^{15}$), the size of the sets $A$ and $B$.

The second line contains $N$ different integers $a_i$ (0ドル ≤ a_i < 2^{15}$), the elements of the set $A$.

The third line contains $N$ different integers $b_i$ (0ドル ≤ b_i < 2^{15}$), the elements of the set $B$.

출력

In the first line, print the number of required moves.

In the remaining lines, print the numbers $x$ and $y$ (0ドル ≤ x, y < 2^{15}$) – we change the number $x$ from set $A$ to the number $y$. The numbers $x$ and $y$ must differ by exactly one bit, and $x \in A$ and $y \not\in A$ must hold at the moment we execute the move.

제한

서브태스크

힌트