bitovi — COCI CONTEST_#5
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 24
Algorithms: set, greedy, graph theory, bitmask

# Task 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.

![](_page_0_Picture_4.jpeg)

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 01012. In one move, it can become 13 = 11012, 1 = 00012, 7 = 01112, or 4 = 01002 if we change its 4th, 3rd, 2nd, or 1st 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.

## Input

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<sub>i</sub>* (0 ≤ *a<sub>i</sub>* < 2^15), the elements of the set *A*.

The third line contains *N* different integers *b<sub>i</sub>* (0 ≤ *b<sub>i</sub>* < 2^15), the elements of the set *B*.

## Output

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* ∈ *A* and *y* ∉ *A* must hold at the moment we execute the move.

### Scoring

The number of moves you are allowed to make in all subtasks must not exceed 2^19. It can be shown that a solution always exists within the given constraints.

| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | *a<sub>i</sub>*, *b<sub>i</sub>* ≤ 2^14 |
| 2 | 15 | *N* ≤ 7 |
| 3 | 30 | *N* ≤ 2^7 |
| 4 | 15 | No additional constraints |

![](_page_1_Picture_0.jpeg)

## Examples

| Input | Input | Input |
|---|---|---|
| 3  0 1 2  1 2 3 | 3  4 8 31  0 4 8 | 5  0 1 2 4 5  7 6 5 3 2 |
| Output | Output | Output |
| 2  1 3  0 1 | 5  31 30  30 28  28 24  24 16  16 0 | 9  1 3  3 7  0 1  1 0  2 6  0 2  7 3  5 7  4 5 |

#### Clarification of the first example:

If we first make the move 0 1, and then 1 3, between these two moves, set *A* would have two identical elements, which the task does not allow. Another possible solution is 2 3, 0 2.

#### Clarification of the second example:

31 = 111112. By removing bits from least to most significant, we obtain the numbers 30, 28, 24, 16, and 0 in sequence. After all moves, set *A* becomes equal to set *B*.

Starter code: