Вам задан некоторый текст \(t\) и набор из \(n\) строк \(s_1, s_2, \dots, s_n\).
За один ход вы можете выбрать любое вхождение любой строки \(s_i\) в текст \(t\) и покрасить соответствующие символы текста в красный цвет. Например, если \(t=\texttt{bababa}\) и \(s_1=\texttt{ba}\), \(s_2=\texttt{aba}\), то за один ход можно получить \(t=\color{red}{\texttt{ba}}\texttt{baba}\), \(t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}\) или \(t=\texttt{bab}\color{red}{\texttt{aba}}\).
Вы хотите сделать все буквы текста \(t\) красными. При повторной покраске буквы в красный цвет, она остаётся красной.
В примере выше достаточно три хода:
- Перекрасим в красный цвет \(t[2 \dots 4]=s_2=\texttt{aba}\), получим \(t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}\);
- Перекрасим в красный цвет \(t[1 \dots 2]=s_1=\texttt{ba}\), получим \(t=\color{red}{\texttt{baba}}\texttt{ba}\);
- Перекрасим в красный цвет \(t[4 \dots 6]=s_2=\texttt{aba}\), получим \(t=\color{red}{\texttt{bababa}}\).
Каждая строка \(s_i\) может применяться произвольное количество раз (или не применяться вообще). Вхождения для покраски могут пересекаться произвольным образом.
Определите, какое минимальное количество ходов надо сделать, чтобы покрасить все буквы \(t\) в красный цвет и как для этого надо совершать ходы. Если сделать все буквы текста \(t\) красными невозможно, то выведите -1.
Выходные данные
Для каждого набора входных данных выведите ответ на отдельной строке.
Если невозможно сделать все буквы текста красными, то выведите единственную строку, содержащую число -1.
Иначе, на первой строке выведите число \(m\) — минимальное количество ходов, которые потребуются, чтобы сделать все буквы \(t\) красными.
Затем в последующих \(m\) строках выведите пары чисел: \(w_j\) и \(p_j\) (\(1 \le j \le m\)), которые обозначают, что строка с индексом \(w_j\) была использована как подстрока для покрытия вхождения, начинающегося в тексте \(t\) с позиции \(p_j\). Пары можно выводить в любом порядке.
Если вариантов ответа несколько, выведите любой из них.
Примечание
Первый набор входных данных разобран в условии задачи.
Во втором наборе входных данных невозможно сделать все буквы текста красными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb
|
3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13
|