D. Покрась вхождениями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан некоторый текст $$$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.

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

Первая строка входных данных содержит целое число $$$q$$$ ($$$1 \le q \le 100$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка каждого набора содержит текст $$$t$$$ ($$$1 \le |t| \le 100$$$), состоящий только из строчных латинских букв, где $$$|t|$$$ — длина текста $$$t$$$.

Вторая строка каждого набора содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10$$$) — количество строк в наборе.

Далее следует $$$n$$$ строк, каждая из которых содержит строку $$$s_i$$$ ($$$1 \le |s_i| \le 10$$$), состоящую только из строчных латинских букв, где $$$|s_i|$$$ — длина строки $$$s_i$$$.

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

Для каждого набора входных данных выведите ответ на отдельной строке.

Если невозможно сделать все буквы текста красными, то выведите единственную строку, содержащую число -1.

Иначе, на первой строке выведите число $$$m$$$ — минимальное количество ходов, которые потребуются, чтобы сделать все буквы $$$t$$$ красными.

Затем в последующих $$$m$$$ строках выведите пары чисел: $$$w_j$$$ и $$$p_j$$$ ($$$1 \le j \le m$$$), которые обозначают, что строка с индексом $$$w_j$$$ была использована как подстрока для покрытия вхождения, начинающегося в тексте $$$t$$$ с позиции $$$p_j$$$. Пары можно выводить в любом порядке.

Если вариантов ответа несколько, выведите любой из них.

Пример
Входные данные
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
Примечание

Первый набор входных данных разобран в условии задачи.

Во втором наборе входных данных невозможно сделать все буквы текста красными.