Это простая версия задачи. Различие между двумя версиями заключается в том, что в этой версии не нужно минимизировать число выполняемых операций. Делать взломы можно только в том случае, если решены обе версии задачи.
Даны две перестановки\(^{\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\)).
Выходные данные
Если решения не существует, выведите одно целое число \(-1\).
Иначе сначала выведите целое число \(k\) (\(0 \le k \le 10\,000\)) — число выполняемых операций, а в каждой из последующих \(k\) строк выведите два числа \(i\) и \(j\) (\(1 \le i \le n\), \(1 \le j \le m\)) — числа, выбранные на очередной итерации.
Если существует несколько решений, выведите любое из них.
Обратите внимание: вам не нужно минимизировать число выполненных операций.