Вам дано целое число \(n\).
Определим \(s(n)\) как строку «BAN», повторенную \(n\) раз. Например, \(s(1)\) = «BAN», \(s(3)\) = «BANBANBAN». Заметим, что длина строки \(s(n)\) равна \(3n\).
Рассмотрим \(s(n)\). Вы можете выполнить следующую операцию над \(s(n)\) любое количество раз (возможно, нулевое):
- Выберите любые два различных индекса \(i\) и \(j\) \((1 \leq i, j \leq 3n, i \ne j)\).
- Затем поменяйте местами \(s(n)_i\) и \(s(n)_j\).
Вы хотите, чтобы строка «BAN» не встречалась в \(s(n)\) как подпоследовательность. Какое наименьшее количество операций нужно выполнить для достижения этой цели? Также найдите одну такую кратчайшую последовательность операций.
Строка \(a\) является подпоследовательностью строки \(b\), если \(a\) можно получить из \(b\) путем удаления нескольких (возможно, нуля или всех) символов.
Выходные данные
Для каждого набора входных данных в первой строке выведите \(m\) (\(0 \le m \le 10^5\)) — минимально необходимое количество операций. Гарантируется, что цель всегда достижима максимум за \(10^5\) операций при ограничениях задачи.
Затем выведите \(m\) строк. В \(k\)-й из этих строк должны содержаться два целых числа \(i_k\), \(j_k\) \((1\leq i_k, j_k \leq 3n, i_k \ne j_k)\), обозначающие, что вы хотите поменять местами символы с индексами \(i_k\) и \(j_k\) на \(k\)-й операции.
После всех \(m\) операций «BAN» не должно встречаться в \(s(n)\) как подпоследовательность.
Если существует несколько возможных ответов, выведите любой.
Примечание
В первом наборе входных данных, \(s(1) = \) «BAN», мы можем поменять местами \(s(1)_1\) и \(s(1)_2\), преобразуя \(s(1)\) в «ABN», которая не содержит «BAN» в качестве подпоследовательности.
Во втором наборе входных данных, \(s(2) = \) «BANBAN», мы можем поменять местами \(s(2)_2\) и \(s(2)_6\), преобразуя \(s(2)\) в «BNNBAA», которая не содержит «BAN» в качестве подпоследовательности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
2
|
1
1 2
1
2 6
|