G. Омкар и пироги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Омкара есть поднос для пирогов с $$$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$$$.

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

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq m \leq n \leq 10^6$$$ и $$$2 \leq k \leq 20$$$) — число эльфов, минимальную длину подотрезка и число мест в подносе Омкара соответственно.

Вторая и третья строки содержат по строке длиной $$$k$$$, состоящей из $$$0$$$ и $$$1$$$, которые представляют собой начальное расположение пирогов и идеальное расположение пирогов; $$$j$$$-й символ в каждой строке равен $$$0$$$, если $$$j$$$-е место в расположении содержит шоколадный пирог, и равен $$$1$$$, если $$$j$$$-е место в расположении содержит тыквенный пирог. Не гарантируется, что две строки имеют одинаковое количество $$$0$$$ или одинаковое количество $$$1$$$.

Ниже следуют $$$n$$$ строк. $$$j$$$-я из этих строк содержит два целых числа $$$a_j$$$ и $$$b_j$$$, ($$$1 \leq a_j, b_j \leq k$$$, $$$a_j \neq b_j$$$), которые указывают на то, что $$$j$$$-й эльф слева может поменять местами пироги в подносе на позициях $$$a_j$$$ и $$$b_j$$$.

Выходные данные

Выводите две строки.

Первая строка должна содержать одно целое $$$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$$$ позиций, в которых тот же тип пирога, что и в идеальном расположении.

Если ответов несколько, то можно вывести любой из них.

Примеры
Входные данные
4 2 5
11000
00011
1 3
3 5
4 2
3 4
Выходные данные
5
1 3
Входные данные
4 3 5
11000
00011
1 3
1 5
2 4
1 5
Выходные данные
3
1 4
Примечание

В первом примере, изменения будут проходить вот так:

  • Поменяйте $$$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$$$.