CF1882E1.Two Permutations (Easy Version)

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).

这是该问题的简单版本。两个版本的区别在于：在此版本中，你无需最小化操作次数。仅当两个版本的问题均被解决时，你才可以进行 Hack。

你有两个排列$^{\dagger}$：$p_{1}, p_{2}, \ldots, p_{n}$（由整数 $1$ 到 $n$ 构成）和 $q_{1}, q_{2}, \ldots, q_{m}$（由整数 $1$ 到 $m$ 构成）。初始时，对 $i=1, 2, \ldots, n$，有 $p_{i}=a_{i}$；对 $j = 1, 2, \ldots, m$，有 $q_{j} = b_{j}$。你可以对这两个排列执行如下操作若干次（也可以不执行）。

每次操作包含以下三个步骤：

• 选择满足 $1 \le i \le n$ 和 $1 \le j \le m$ 的整数 $i$、$j$；
• 将排列 $p$ 以 $p_i$ 为轴点划分为三部分：左部由元素 $p_1, p_2, \ldots, p_{i-1}$ 构成（该部分可能为空），中部为单个元素 $p_i$，右部为 $p_{i+1}, p_{i+2}, \ldots, p_n$（该部分可能为空）。接下来，交换该划分中的左部与右部。形式化地，此步之后，$p$ 变为 $p_{i+1}, p_{i+2}, \ldots, p_{n}, p_{i}, p_{1}, p_{2}, \ldots, p_{i-1}$。新得到的 $p$ 的元素将从下标 $1$ 开始重新编号；
• 对 $q$ 在索引 $j$ 处执行相同的变换。形式化地，此步之后，$q$ 变为 $q_{j+1}, q_{j+2}, \ldots, q_{m}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1}$。新得到的 $q$ 的元素将从下标 $1$ 开始重新编号。

你的目标是同时使得对所有 $i=1, 2, \ldots, n$ 满足 $p_{i}=i$，且对所有 $j = 1, 2, \ldots, m$ 满足 $q_{j} = j$。

请找出任意一种在至多 $10\,000$ 次操作内达成目标的方法，或判定不存在这样的方法。请注意，你无需最小化操作次数。

可以证明：若目标可达，则必存在一种至多使用 $10\,000$ 次操作的方案。

$^{\dagger}$ 长度为 $k$ 的排列是指由 $1$ 到 $k$ 中 $k$ 个互异整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（此时 $k=3$，但数组中出现了 $4$）。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2500$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \le b_i \le m$）。

保证 $a$ 和 $b$ 均为排列。

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.

如果无解，请输出单个整数 $-1$。

否则，先输出一个整数 $k$（$0 \le k \le 10\,000$）—— 表示需执行的操作次数，随后输出 $k$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i \le n$，$1 \le j \le m$）—— 表示该次操作所选的下标。

若存在多个解，输出任意一个即可。

请注意，你无需最小化操作次数。

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.

在第一个例子中，我们可以在 $2$ 次操作内达成目标：

1. 第一次操作中，选择 $i = 3$、$j = 4$。操作后，$p$ 变为 $[3, 2, 1]$，$q$ 变为 $[3, 4, 5, 2, 1]$。
2. 第二次操作中，选择 $i = 2$、$j = 4$。操作后，$p$ 变为 $[1, 2, 3]$，$q$ 变为 $[1, 2, 3, 4, 5]$。

在第三个例子中，无法达成目标。