Problem Description

Which comes first, the chicken or the egg? Is it better to be a millionaire for a hundred years or to live in poverty for seven days? How does one become a chess master? How do you raise a blind? How do you pass the final exam? How do you train a dragon? These are some interesting questions that we can think about after the competition, but now we pose a less interesting computer science problem.

Given two sets of numbers, \( A \) and \( B \), both of size \( N \). In each operation, you can select any element from set \( A \) and change one arbitrary bit in its binary representation. The resulting number must not be an element of the original set \( A \).

For example, the binary representation of the number \( 5 \) is \( 0101_2 \). With one operation, it can be transformed into \( 13 = 1101_2 \), \( 1 = 0001_2 \), \( 7 = 0111_2 \), or \( 4 = 0100_2 \).

Determine a series of operations such that set \( A \) becomes identical to set \( B \). Two sets are considered identical if they are of the same size and set \( A \) contains no elements that are not in set \( B \).

Note: The number of operations does not need to be minimal, but must satisfy the constraints 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 positive integers \( a_i \) (\( 1 \le a_i < 2^{15} \)), representing the elements of set \( A \).

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

Output Format

The first line should output the number of operations, which should not exceed \( 2^{19} \).

The following lines should each contain two integers \( x, y \) (\( 0 \le x, y < 2^{15} \)), indicating that \( x \) in set \( A \) is changed to \( y \). \( x \) and \( y \) must differ by exactly one bit in their binary representations, and \( x \) must be in \( A \) while \( y \) must not be in \( A \).

Sample Input and Output

Input Sample #1

3
0 1 2
1 2 3

Output Sample #1

2
1 3
0 1

Input Sample #2

3
4 8 31
0 4 8

Output Sample #2

5
31 30
30 28
28 24
24 16
16 0

Input Sample #3

5
0 1 2 4 5
7 6 5 3 2

Output Sample #3

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

Notes/Hints

Sample Explanation 1

If we first operate on \( 0 \ 1 \) and then on \( 1 \ 3 \), between the two operations, set \( A \) will have two identical elements, which is not allowed. Another possible solution is \( 2 \ 3 \), \( 0 \ 2 \).

Sample Explanation 2

\( 31 = 11111_2 \). By modifying from the least significant bit to the most significant bit, we can sequentially obtain \( 30, 28, 24, 16 \), and \( 0 \). After all operations, \( A \) and \( B \) are identical.

Subtasks

见题面 Input 部分

见题面 Output 部分