Codeforces Round 270 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

math

matrices

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Design Tutorial: Change the Goal

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are some tasks which have the following structure: you are given a model, and you can do some operations, you should use these operations to achive the goal. One way to create a new task is to use the same model and same operations, but change the goal.

Let's have a try. I have created the following task for Topcoder SRM 557 Div1-Hard: you are given *n* integers *x*_{1}, *x*_{2}, ..., *x*_{n}. You are allowed to perform the assignments (as many as you want) of the following form *x*_{i} ^= *x*_{j} (in the original task *i* and *j* must be different, but in this task we allow *i* to equal *j*). The goal is to maximize the sum of all *x*_{i}.

Now we just change the goal. You are also given *n* integers *y*_{1}, *y*_{2}, ..., *y*_{n}. You should make *x*_{1}, *x*_{2}, ..., *x*_{n} exactly equal to *y*_{1}, *y*_{2}, ..., *y*_{n}. In other words, for each *i* number *x*_{i} should be equal to *y*_{i}.

Input

The first line contains an integer *n* (1 ≤ *n* ≤ 10000). The second line contains *n* integers: *x*_{1} to *x*_{n} (0 ≤ *x*_{i} ≤ 10^{9}). The third line contains *n* integers: *y*_{1} to *y*_{n} (0 ≤ *y*_{i} ≤ 10^{9}).

Output

If there is no solution, output -1.

If there is a solution, then in the first line output an integer *m* (0 ≤ *m* ≤ 1000000) – the number of assignments you need to perform. Then print *m* lines, each line should contain two integers *i* and *j* (1 ≤ *i*, *j* ≤ *n*), which denote assignment *x*_{i} ^= *x*_{j}.

If there are multiple solutions you can print any of them. We can prove that under these constraints if there exists a solution then there always exists a solution with no more than 10^{6} operations.

Examples

Input

2

3 5

6 0

Output

2

1 2

2 2

Input

5

0 0 0 0 0

1 2 3 4 5

Output

-1

Input

3

4 5 6

1 2 3

Output

5

3 1

1 2

2 2

2 3

3 1

Input

3

1 2 3

4 5 6

Output

-1

Note

Assignment *a* ^= *b* denotes assignment *a* = *a* ^ *b*, where operation "^" is bitwise XOR of two integers.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 12:43:24 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|