E1. Две перестановки (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Различие между двумя версиями заключается в том, что в этой версии не нужно минимизировать число выполняемых операций. Делать взломы можно только в том случае, если решены обе версии задачи.

Даны две перестановки$$$^{\dagger}$$$ $$$p_{1}, p_{2}, \ldots, p_{n}$$$ (чисел от $$$1$$$ до $$$n$$$) и $$$q_{1}, q_{2}, \ldots, q_{m}$$$ (чисел от $$$1$$$ до $$$m$$$). Изначально $$$p_{i}=a_{i}$$$ для всех $$$i=1, 2, \ldots, n$$$, а также $$$q_{j} = b_{j}$$$ для всех $$$j = 1, 2, \ldots, m$$$. Вы можете применять к перестановкам следующую операцию несколько раз (возможно, ни одного).

За одну операцию $$$p$$$ и $$$q$$$ меняются в соответствии с тремя следующими шагами:

  • Вы выбираете целые числа $$$i$$$, $$$j$$$, такие что $$$1 \le i \le n$$$ and $$$1 \le j \le m$$$.
  • Перестановка $$$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$$$.

Ваша цель — добиться одновременного выполнения равенств $$$p_{i}=i$$$ для всех $$$i=1, 2, \ldots, n$$$, а также $$$q_{j} = j$$$ для всех $$$j = 1, 2, \ldots, m$$$.

Найдите произвольный способ добиться этого, используя не более $$$10\,000$$$ операций, или сообщите, что это невозможно. Обратите внимание: вам не нужно минимизировать число выполненных операций.

Можно показать, что если цель достижима, то существует способ добиться её, используя не более $$$10\,000$$$ операций.

$$$^{\dagger}$$$ Перестановкой длины $$$k$$$ является массив, состоящий из $$$k$$$ различных целых чисел от $$$1$$$ до $$$k$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$k=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Первая строка содержит два целых числа $$$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$$$ являются перестановками.

Выходные данные

Если решения не существует, выведите одно целое число $$$-1$$$.

Иначе сначала выведите целое число $$$k$$$ ($$$0 \le k \le 10\,000$$$) — число выполняемых операций, а в каждой из последующих $$$k$$$ строк выведите два числа $$$i$$$ и $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) — числа, выбранные на очередной итерации.

Если существует несколько решений, выведите любое из них.

Обратите внимание: вам не нужно минимизировать число выполненных операций.

Примеры
Входные данные
3 5
2 1 3
5 2 1 4 3
Выходные данные
2
3 4
2 4
Входные данные
4 4
3 4 2 1
2 4 1 3
Выходные данные
5
4 2
3 3
1 4
3 2
4 1
Входные данные
2 2
1 2
2 1
Выходные данные
-1
Примечание

В первом тесте можно достичь цели за $$$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]$$$.

В третьем тесте достичь цели невозможно.