E. Маша-забываша
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маша познакомилась с новым другом и узнала его номер телефона — $$$s$$$. Она хочет как можно скорее запомнить его. Номер телефона — это строка длины $$$m$$$, которая состоит из цифр от $$$0$$$ до $$$9$$$. Допустимо, что телефон начинается с 0.

Маша уже знает $$$n$$$ номеров телефонов (все номера имеют одинаковую длину $$$m$$$). Ей будет проще запомнить новый номер, если строку $$$s$$$ представить как отрезки уже известных ей номеров. Каждый такой отрезок должен быть длины не менее $$$2$$$, иначе отрезков будет слишком много, и Маша запутается.

Например, Маше нужно запомнить номер: $$$s = $$$ «12345678» и она уже знает $$$n = 4$$$ номера: «12340219», «20215601», «56782022», «12300678». Можно представить $$$s$$$ как $$$3$$$ отрезка: «1234» из первого номера, «56» из второго номера и «78» из третьего номера. Есть и другие способы представления $$$s$$$.

Маша обратилась к вам за помощью, она просит вас разбить строку $$$s$$$ на отрезки длины $$$2$$$ или более из уже известных ей номеров. Если существует несколько возможных ответов, выведите любой из них.

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

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Перед каждым набором в тесте записана пустая строка. Далее идёт строка, которая содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^3$$$) — количество номеров, которые знает Маша и количество цифр в каждом номере. Затем следуют $$$n$$$ строк, $$$i$$$-я из которых описывает $$$i$$$-й номер, который знает Маша. Следующая строка содержит номер телефона её нового друга $$$s$$$.

Среди заданных $$$n+1$$$ телефонов могут быть дубликаты (одинаковые телефоны).

Гарантируется, что сумма значений $$$n \cdot m$$$ ($$$n$$$ умножить на $$$m$$$) по всем наборам входных данных в тесте не превосходит $$$10^6$$$.

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

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

В случае положительного ответа далее должны следовать $$$k$$$ строк, содержащие тройки чисел $$$l, r, i$$$. Такая тройка обозначает, что очередные $$$r-l+1$$$ цифр номера $$$s$$$ равны отрезку (подстроке) с границами $$$[l, r]$$$ телефона под номером $$$i$$$. И телефоны и цифры в них нумеруются от $$$1$$$. Обратите внимание, что $$$r-l+1 \ge 2$$$ для всех $$$k$$$ строк.

Пример
Входные данные
5

4 8
12340219
20215601
56782022
12300678
12345678

2 3
134
126
123

1 4
1210
1221

4 3
251
064
859
957
054

4 7
7968636
9486033
4614224
5454197
9482268
Выходные данные
3
1 4 1
5 6 2
3 4 3
-1
2
1 2 1
2 3 1
-1
3
1 3 2
5 6 3
3 4 1
Примечание

Первый тестовый случай соответствует примеру из условия.

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

В третьем случае можно получить отрезки «12» и «21» из первого номера телефона.