У Омкара есть поднос для пирогов с \(k\) местами (\(2 \leq k \leq 20\)). Каждое место на подносе содержит либо шоколадный пирог, либо тыквенный пирог. Омкару не нравится, как пироги расположены в настоящее время, и у него есть другое идеальное расположение, которое он предпочел бы этому.
Чтобы помочь Омкару, \(n\) эльфов построились в очередь на замену пирогов на подносе. \(j\)-й слева эльф способен поменять пироги на позициях \(a_j\) и \(b_j\) местами.
Чтобы максимально приблизиться к своему идеальному расположению, Omkar может выбрать последовательный подотрезок эльфов и затем пропустить свой поднос через этот подотрезок, начиная слева. Однако, поскольку эльфы приложили столько усилий, чтобы собраться в строку, они просят, чтобы выбранный Омкаром подотрезок содержал как минимум \(m\) (\(1 \leq m \leq n\)) эльфов.
Формально, Omkar может выбрать два целых числа \(l\) и \(r\), удовлетворяющих \(1 \leq l \leq r \leq n\) и \(r - l + 1 \geq m\), после чего сначала будут поменяны пироги в позициях \(a_l\) и \(b_l\), затем пироги в позициях \(a_{l + 1}\) и \(b_{l + 1}\) и т.д. пока, наконец, не будут поменяны местами пироги \(a_r\) и \(b_r\).
Помогите Омкару выбрать подотрезок эльфов таким образом, чтобы количество позиций в итоговой расстановке Омкара, содержащих тот же тип пирога, что и в его идеальной расстановке, было максимально возможным. Обратите внимание, что поскольку Омкар обладает большим воображением, может случиться так, что количество пирогов каждого типа в его первоначальном расположении и в его идеальном расположении не совпадают.
Выходные данные
Выводите две строки.
Первая строка должна содержать одно целое \(s\) (\(0 \leq s \leq k\)), равное количеству позиций, которые содержат один и тот же тип пирога в окончательном расположении Омкара и в идеальном расположении Омкара; \(s\) должно быть максимально возможным.
Вторая строка должна содержать два целых числа \(l\) и \(r\), удовлетворяющих \(1 \leq l \leq r \leq n\) и \(r - l + 1 \geq m\), обозначающих, что Омкар должен пропустить свой поднос через подотрезок \(l, l + 1, \dots, r\), чтобы добиться конечного расположения в котором есть \(s\) позиций, в которых тот же тип пирога, что и в идеальном расположении.
Если ответов несколько, то можно вывести любой из них.
Примечание
В первом примере, изменения будут проходить вот так:
- Поменяйте \(1\) и \(3\): 11000 становится 01100
- Поменяйте \(3\) и \(5\): 01100 становится 01001
- Поменяйте \(4\) и \(2\): 01001 становится 00011
Окончательная расстановка такая же, как и у идеального пирога
00011, поэтому есть
\(5\) позиций с тем же типом пирога, что и в оптимальной.
Во втором примере, изменения будут идти вот так:
- Поменяйте \(1\) и \(3\): 11000 становится 01100
- Поменяйте \(1\) и \(5\): 01100 становится 01100
- Поменяйте \(4\) и \(2\): 01100 становится 00110
- Поменяйте \(1\) и \(5\): 00110 становится 00110
Окончательная расстановка имеет
\(3\) позиции с тем же типом пирога, что и идеальная расстановка
00011, это позиции
\(1\),
\(2\) и
\(4\). В этом случае подотрезок эльфов
\((l, r) = (2, 3)\) более оптимален, но этот подотрезок имеет только длину
\(2\) и поэтому не удовлетворяет ограничению, заключающемуся в том, что подотрезок должен иметь длину не менее
\(m = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 5
11000
00011
1 3
3 5
4 2
3 4
|
5
1 3
|
|
2
|
4 3 5
11000
00011
1 3
1 5
2 4
1 5
|
3
1 4
|