Two permutations of balls

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk likes to play with multicolored balls.

He has 2 rows of balls. Each row contains \(n\) balls, with numbers between 1 and \(n\) written on them such that the numbers in each row form a permutation. In the first row all balls are blue, in the second they are yellow.

In 1 move, you can choose one ball in the first row, one ball in the second row, and swap them. Help Zenyk in at most \(n + 1\) moves to reach a situation where:

• in the first row all balls are blue

• in the second row all balls are yellow

• the permutations on the balls in the first and second row are identical

Input

The first line contains a single integer \(n\) — the number of balls in each of the rows.

The second line contains \(n\) positive integers \(p_1, p_2, \ldots, p_n\) — the permutation of blue balls.

The third line contains \(n\) positive integers \(q_1, q_2, \ldots, q_n\) — the permutation of yellow balls.

Output

In the first line output a single integer \(k\) — the number of moves you want to make. In each of the next \(k\) lines output two numbers \(a_i\) and \(b_i\), which denote swapping the ball at position \(a_i\) in the first row and the ball at position \(b_i\) in the second row. \(k\) must not exceed \(n + 1\).

It is guaranteed that under the given constraints the answer always exists. If there are multiple possible sequences of moves, output any.

Constraints

\(1 \le n \le 2 \cdot 10^{5}\),

\(1 \le p_i, q_i \le n\),

The arrays \([p_1, p_2, \ldots, p_n]\) and \([q_1, q_2, \ldots, q_n]\) are permutations.

Samples

Input (stdin) сopy	Output (stdout) сopy
6 2 3 4 1 6 5 6 3 1 2 4 5	7 3 4 5 4 4 4 3 4 1 1 1 4 1 1

Notes

Explanation of the example (symbols + and - correspond to blue and yellow balls):

• Input permutations: \([2_{+} \quad 3_{+} \quad 4_{+} \quad 1_{+} \quad 6_{+} \quad 5_{+}]\) and \([6_{-} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]\);

• Move 1 \(a_1 = 3, b_1 = 4\): \([2_{+} \quad 3_{+} \quad 2_{-} \quad 1_{+} \quad 6_{+} \quad 5_{+}]\) and \([6_{-} \quad 3_{-} \quad 1_{-} \quad 4_{+} \quad 4_{-} \quad 5_{-}]\);

• Move 2 \(a_2 = 5, b_2 = 4\): \([2_{+} \quad 3_{+} \quad 2_{-} \quad 1_{+} \quad 4_{+} \quad 5_{+}]\) and \([6_{-} \quad 3_{-} \quad 1_{-} \quad 6_{+} \quad 4_{-} \quad 5_{-}]\);

• Move 3 \(a_3 = 4, b_3 = 4\): \([2_{+} \quad 3_{+} \quad 2_{-} \quad 6_{+} \quad 4_{+} \quad 5_{+}]\) and \([6_{-} \quad 3_{-} \quad 1_{-} \quad 1_{+} \quad 4_{-} \quad 5_{-}]\);

• Move 4 \(a_4 = 3, b_4 = 4\): \([2_{+} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]\) and \([6_{-} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]\);

• Move 5 \(a_5 = 1, b_5 = 1\): \([6_{-} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]\) and \([2_{+} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]\);

• Move 6 \(a_6 = 1, b_6 = 4\): \([2_{-} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]\) and \([2_{+} \quad 3_{-} \quad 1_{-} \quad 6_{-} \quad 4_{-} \quad 5_{-}]\);

• Move 7 \(a_7 = 1, b_7 = 1\): \([2_{+} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]\) and \([2_{-} \quad 3_{-} \quad 1_{-} \quad 6_{-} \quad 4_{-} \quad 5_{-}]\).