Background

Translated from COCI 2023/2024 Contest #5 T2 “Bitovi”.

Problem Description

Which came first, the chicken or the egg? Is it better to live as a millionaire for one hundred years, or spend seven days in poverty? How do you become a chess master? How do you pull up blinds? How do you pass final exams? How do you train a dragon? These are all interesting questions we can think about after the contest, but now we will ask a less interesting computer science question.

You are given two sets of numbers $A$ and $B$, both of size $N$. In one operation, you may choose any element from set $A$ and change any one bit in its binary representation. The resulting number must not be an element of set $A$ before the change.

For example, the binary representation of $5$ is $0101_2$. With one operation, it can become $13=1101_2$, $1=0001_2$, $7=0111_2$, or $4=0100_2$.

Find a sequence of operations that transforms set $A$ into set $B$. Two sets are considered equal if they have the same size and there is no element in $A$ that does not belong to $B$.

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

Input Format

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

The second line contains $N$ distinct integers $a_i$ ($0 \le a_i < 2^{15}$), the elements of set $A$.

The third line contains $N$ distinct integers $b_i$ ($0 \le b_i < 2^{15}$), the elements of set $B$.

Output Format

On the first line, output the number of operations, not exceeding $2^{19}$.

Then output several lines. Each line should contain $x, y$ ($0 \le x, y < 2^{15}$), meaning that you change $x$ in set $A$ into $y$. The binary representations of $x$ and $y$ must differ in exactly one bit. Also, it must hold that $x \in A$ and $y \not\in A$.

3
0 1 2
1 2 3

2
1 3
0 1

3
4 8 31
0 4 8

5
31 30
30 28
28 24
24 16
16 0

5
0 1 2 4 5
7 6 5 3 2

9
1 3
3 7
0 1
1 0
2 6
0 2
7 3
5 7
4 5

Hint

Sample Explanation 1

If we first perform $0\ 1$ and then $1\ 3$, then between the two operations, set $A$ will contain two equal elements, which is not allowed. Another possible solution is $2\ 3$, $0\ 2$.

Sample Explanation 2

$31=11111_2$. If we modify bits from the least significant bit to the most significant bit, we can obtain $30, 28, 24, 16$, and $0$ in order. After all operations, $A$ and $B$ are the same.

Subtasks

Translated by ChatGPT 5