Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вывести все операции, которые нужно сделать. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Вам даны \(n\) массивов, каждый из которых имеет длину \(m\). Обозначим \(j\)-й элемент \(i\)-го массива как \(a_{i, j}\). Гарантируется, что все \(a_{i, j}\) попарно различны. За одну операцию вы можете сделать следующее:
- Выбрать какое-то целое число \(i\) (\(1 \le i \le n\)) и целое число \(x\) (\(1 \le x \le 2 \cdot n \cdot m\)).
- Для всех целых чисел \(k\) от \(i\) до \(n\) в порядке возрастания сделать следующее:
- Добавить элемент \(x\) в начало \(k\)-го массива.
- Присвоить \(x\) значение, равное последнему элементу в \(k\)-м массиве.
- Удалить последний элемент из \(k\)-го массива.
Другими словами, вы можете вставить элемент в начало любого массива, после чего все элементы в этом и всех следующих массивах сдвигаются на один вправо. При этом последний элемент последнего массива удаляется.
Также вам дано описание массивов, которые необходимо получить после всех операций. То есть после выполнения операций \(j\)-й элемент в \(i\)-м массиве должен быть равен \(b_{i, j}\). Гарантируется, что все \(b_{i, j}\) попарно различны.
Определите минимальное количество операций, которое необходимо выполнить, чтобы получить нужные массивы, а также выведите саму последовательность всех операций.
Выходные данные
Для каждого набора входных данных выведите в первой строке единственное целое число — минимальное количество операций, которые необходимо выполнить.
Далее, для каждой операции выведите два целых числа \(i\) и \(x\) (\(1 \le i \le n\), \(1 \le x \le 2 \cdot n \cdot m\)) — номер массива, куда вставляется элемент, и значение элемента, соответственно.
Если существует несколько возможных последовательностей с минимальным количеством операций, выведите любую из них.
Примечание
В первом наборе входных данных подходит следующая последовательность из \(3\) операций:
- Применим операцию к первому массиву с \(x = 1\). Тогда в начало первого массива добавится элемент \(1\), а значение \(x\) станет равным \(6\). Последний элемент удалится, и первый массив будет иметь вид \([1, 2]\). Далее, элемент \(x\) добавляется в начало второго массива, и значение \(x\) становится равным \(4\). Последний элемент второго массива удаляется, и оба массива имеют вид \([1, 2]\) и \([6, 3]\) соответственно после первой операции.
- Применим операцию ко второму массиву с \(x = 8\). Тогда первый массив не изменится, и оба массива будут иметь вид \([1, 2]\) и \([8, 6]\) соответственно.
- Применим операцию ко второму массиву при \(x = 7\), тогда оба массива будут иметь необходимый вид \([1, 2]\) и \([7, 8]\) соответственно.
Во втором наборе входных данных получить нужный массив можно только за \(5\) операций.
В третьем наборе входных данных подходит следующая последовательность из \(3\) операций:
- Применим операцию с \(x = 11\) к первому массиву.
- Применим операцию с \(x = 12\) ко второму массиву.
- Применим операцию с \(x = 13\) к третьему массиву.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2
2 6
3 4
1 2
7 8
1 5
5 4 1 2 3
5 4 3 2 1
3 3
1 2 3
4 5 6
7 8 9
11 1 2
12 3 4
13 5 6
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 1 2 3
4 18 5 6
7 19 8 20
9 21 22 10
|
3
1 1
2 8
2 7
5
1 1
1 2
1 3
1 4
1 5
3
1 11
2 12
3 13
6
3 20
2 18
3 19
4 22
4 21
1 17
|