Problem Description

Given two sequences of positive integers of length $N-1$, $A=(A_2,A_3,\ldots,A_N)$ and $B=(B_2,B_3,\ldots,B_N)$, (note that the indices start from 2), determine if there is a way to make $A=B$ by performing the following operation up to $10^6$ times, and if so, construct one such method.

• Choose an integer $i\ (2\ \le\ i)$ and its multiple $j$, and swap the values of $A_i$ and $A_j$. Note that $i=j$ is allowed.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_2 $ $ A_3 $ $\ldots$ $ A_N $ $ B_2 $ $ B_3 $ $\ldots$ $ B_N $

Output Format

If there exists a way to make $A=B$, output in the following format:

$ M $ $ I_1 $ $ J_1 $ $ I_2 $ $ J_2 $ $\vdots$ $ I_M $ $ J_M $

Here, $M\ (0\ \le\ M\ \le\ 10^6)$ represents the number of operations, and $I_k,J_k$ represent the $i,j$ chosen in the $k\ (1\ \le\ k\ \le\ M)$th operation.

If there is no way to make $A=B$, output -1.

Sample Input and Output

Sample Input #1

4
3 2 4
4 2 3

Sample Output #1

1
2 4

Sample Input #2

2
3
4

Sample Output #2

-1

Sample Input #3

6
4 1 3 2 5
1 5 4 2 3

Sample Output #3

3
3 6
2 4
2 6

Notes/Hints

Constraints

• $2\ \le\ N\ \le\ 50000$
• $1\ \le\ A_i,B_i\ \le\ 50000\ (2\ \le\ i\ \le\ N)$
• All inputs are integers

见题面 Input 部分

见题面 Output 部分