На планете AMI-1511 живёт мальчик Айрат. У каждого из жителей этой планеты есть свое хобби, в частности, Айрат любит бегать, причём не просто так — он мечтает превратить бег в настоящее искусство.
Для начала Айрат хочет сконструировать беговой трек с полотном t. Полотно для трека на AMI-1511 — последовательность из цветных блоков, где каждый блок обозначается строчной английской буквой. Таким образом, любое полотно представляется как строка некоторой длины. К сожалению, блоки отсутствуют в свободной продаже.
Айрат нашёл в магазине неограниченное количество полотен для трека s, а ещё у него есть ножницы и клей. Айрат может купить некоторое количество полотен s, после чего вырезать из каждого ровно один непрерывный кусок (подстроку) и приклеить его в конец своего полотна, при этом он может развернуть новый кусок перед приклеиванием. Помогите Айрату посчитать, сколько минимум полотен s ему нужно купить, какие куски из них вырезать и в каком порядке склеить, чтобы получить желанное полотно t.
Выходные данные
В первой строке выведите минимальное число полотен n или -1, если собрать желанное полотно не представляется возможным.
Если ответ не -1, то в следующих n строках выведите по два числа xi и yi — номера крайних блоков в вырезаемом куске. xi ≤ yi означает, что кусок приклеивается в исходном порядке, а xi > yi — что в развёрнутом. Куски выводите в том порядке, в котором их следует склеивать, чтобы получить строку t.
Примечание
В первом примере строка "cbaabc" = "cba" + "abc".
Во втором примере: "ayrat" = "a" + "yr" + "at".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
cbaabc
|
2
3 1
1 3
|
|
2
|
aaabrytaaa
ayrat
|
3
1 1
6 5
8 7
|
|
3
|
ami
no
|
-1
|