310759: CF1882E1. Two Permutations (Easy Version)

E1. Two Permutations (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The difference between the two versions is that you do not have to minimize the number of operations in this version. You can make hacks only if both versions of the problem are solved.

You have two permutations$^{\dagger}$ $p_{1}, p_{2}, \ldots, p_{n}$ (of integers $1$ to $n$) and $q_{1}, q_{2}, \ldots, q_{m}$ (of integers $1$ to $m$). Initially $p_{i}=a_{i}$ for $i=1, 2, \ldots, n$, and $q_{j} = b_{j}$ for $j = 1, 2, \ldots, m$. You can apply the following operation on the permutations several (possibly, zero) times.

In one operation, $p$ and $q$ will change according to the following three steps:

• You choose integers $i$, $j$ which satisfy $1 \le i \le n$ and $1 \le j \le m$.
• Permutation $p$ is partitioned into three parts using $p_i$ as a pivot: the left part is formed by elements $p_1, p_2, \ldots, p_{i-1}$ (this part may be empty), the middle part is the single element $p_i$, and the right part is $p_{i+1}, p_{i+2}, \ldots, p_n$ (this part may be empty). To proceed, swap the left and the right parts of this partition. Formally, after this step, $p$ will become $p_{i+1}, p_{i+2}, \ldots, p_{n}, p_{i}, p_{1}, p_{2}, \ldots, p_{i-1}$. The elements of the newly formed $p$ will be reindexed starting from $1$.
• Perform the same transformation on $q$ with index $j$. Formally, after this step, $q$ will become $q_{j+1}, q_{j+2}, \ldots, q_{m}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1}$. The elements of the newly formed $q$ will be reindexed starting from $1$.

Your goal is to simultaneously make $p_{i}=i$ for $i=1, 2, \ldots, n$, and $q_{j} = j$ for $j = 1, 2, \ldots, m$.

Find any valid way to achieve the goal using at most $10\,000$ operations, or say that none exists. Please note that you do not have to minimize the number of operations.

It can be proved that if it is possible to achieve the goal, then there exists a way to do so using at most $10\,000$ operations.

$^{\dagger}$ A permutation of length $k$ is an array consisting of $k$ distinct integers from $1$ to $k$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($k=3$ but there is $4$ in the array).

Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2500$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le m$).

It is guaranteed that $a$ and $b$ are permutations.

Output

If there is no solution, print a single integer $-1$.

Otherwise, print an integer $k$ ($0 \le k \le 10\,000$) — the number of operations to perform, followed by $k$ lines, each containing two integers $i$ and $j$ ($1 \le i \le n$, $1 \le j \le m$) — the integers chosen for the operation.

If there are multiple solutions, print any of them.

Please note that you do not have to minimize the number of operations.

ExamplesInput

3 5
2 1 3
5 2 1 4 3

Output

2
3 4
2 4

Input

4 4
3 4 2 1
2 4 1 3

Output

5
4 2
3 3
1 4
3 2
4 1

Input

2 2
1 2
2 1

Output

-1

Note

In the first example, we can achieve the goal within $2$ operations:

1. In the first operation, choose $i = 3$, $j = 4$. After this, $p$ becomes $[3, 2, 1]$ and $q$ becomes $[3, 4, 5, 2, 1]$.
2. In the second operation, choose $i = 2$, $j = 4$. After this, $p$ becomes $[1, 2, 3]$ and $q$ becomes $[1, 2, 3, 4, 5]$.

In the third example, it is impossible to achieve the goal.

题目大意：给定两个排列p和q，长度分别为n和m。你可以对排列进行多次以下操作：选择整数i和j，将排列p（或q）分为三部分，然后交换左右两部分。目标是使p和q分别变为1到n和1到m的有序排列。需要找到一种方法，在最多10000次操作内实现目标，或者确定不存在这样的方法。

输入数据格式：第一行包含两个整数n和m（1≤n,m≤2500）。第二行包含n个整数a1,a2,…,an（1≤ai≤n）。第三行包含m个整数b1,b2,…,bm（1≤bi≤m）。保证a和b是排列。

输出数据格式：如果不存在解决方案，输出一个整数-1。否则，输出一个整数k（0≤k≤10000）表示操作次数，接下来k行，每行包含两个整数i和j，表示每次操作选择的整数。如果有多个解决方案，输出其中任意一个。题目大意：给定两个排列p和q，长度分别为n和m。你可以对排列进行多次以下操作：选择整数i和j，将排列p（或q）分为三部分，然后交换左右两部分。目标是使p和q分别变为1到n和1到m的有序排列。需要找到一种方法，在最多10000次操作内实现目标，或者确定不存在这样的方法。 输入数据格式：第一行包含两个整数n和m（1≤n,m≤2500）。第二行包含n个整数a1,a2,…,an（1≤ai≤n）。第三行包含m个整数b1,b2,…,bm（1≤bi≤m）。保证a和b是排列。 输出数据格式：如果不存在解决方案，输出一个整数-1。否则，输出一个整数k（0≤k≤10000）表示操作次数，接下来k行，每行包含两个整数i和j，表示每次操作选择的整数。如果有多个解决方案，输出其中任意一个。