Final year is approaching. Shirogane and Shinomiya, both highly prestigious students, have taken the maximum number of courses $N$, choosing the most challenging ones. As a result, their schedules contain the same courses.

Although they have the same courses, the order of the courses in their schedules may vary, with Shirogane's schedule being $A$ and Shinomiya's being $B$. Thus, Shirogane wants to adjust his schedule to match Shinomiya exactly. As the student council president, he has the ability to swap the time slots of any two courses $A_i$ and $A_j$ in his own schedule. However, to avoid suspicion, he must limit the number of swaps to at most $N-1$, ensuring that Shinomiya does not notice the changes in the system.

Since the number of courses is extremely large, he bribes requests your help as the coding club president to write a program that assists him.

Constraints

$3\le N\le {10}^6$

$1\le A_i,B_i\le N$

$A$ is a permutation of $B$.

Subtask 1 [5/15]

$3\le N\le 1000$

Subtask 2 [5/15]

No course appears more than once in Shirogane's schedule. Formally, if $x\ne y$, then $A_x\ne A_y$.

Subtask 3 [5/15]

No additional constraints.

Input Specification

The first line contains an integer $N$, representing the length of their schedules.

The second line contains $N$ space seperated integers, $A$, representing the courses in Shirogane's schedule.

The third line contains $N$ space seperated integers, $B$, representing the courses in Shinomiya's schedule.

Output Specification

On the first line, output one integer $M$, representing the number of swaps you will perform. This number should be at most $N-1$.

On each of the next $M$ lines, output two integers, $A_i$ and $A_j$, representing the indices of the two courses to swap in Shirogane's schedule.

Note: You do not need to find the shortest sequence of swaps. If there are multiple valid solutions, output any of them. Also, it can be proven that it is always possible to make Shirogane's schedule match Shinomiya's in at most $N-1$ swaps.

Sample Input 1

3
3 1 2
1 2 3

Sample Output 1

2
1 2
2 3

Explanation for Sample 1

In the first swap, course $A_1$ and course $A_2$ are swapped in Shirogane's schedule. His schedule is now $[1,3,2]$.

In the second swap, course $A_2$ and course $A_3$ are swapped in Shirogane's schedule. His schedule is now $[1,2,3]$, which matches Shinomiya's.

Sample Input 2

5
2 2 1 1 3
1 1 3 2 2

Sample Output 2

3
3 5
1 5
2 4

Sample Input 3

3
1 1 1
1 1 1

Sample Output 3

0