В Берляндии ураган и это стихийное бедствие не обошло стороной предместье Строксвиль. Вы мчитесь в него, чтобы проверить, всё ли в порядке с вашей любимой строкой. Ураган немного потрепал её, перевернув несколько её непересекающихся подстрок. У вас сохранилась фотография строки до урагана и вы хотите привести её в исходное состояние, перевернув обратно наименьшее возможное число её подстрок, но для этого сперва нужно определиться, какие подстроки нужно перевернуть.
У вас есть строка s — исходное состояние вашей строки и строка t — то, какой она стала после того, как ураган перевернул некоторые её подстроки. Ваша задача выбрать k непересекающихся подстрок строки t таких что если их развернуть, вы получите строку s и число k при этом наименьшее возможное.
Выходные данные
В первой строке выведите число k — наименьшее возможное число подстрок, которые надо перевернуть. В следующих k строках выведите по два числа li, ri в каждой, обозначающие, что нужно перевернуть строку с li по ri символы (строки 1-индексированные). Указанные подстроки не должны пересекаться. Если вариантов ответа несколько, выведите любой. Если решения не существует, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6
|
1
1
2
4
256
3
27
597484987
|