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

Даны две перестановки$$$^{\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$$$.

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

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