Codeforces Round 764 (Div. 3) |
---|
Закончено |
Маша познакомилась с новым другом и узнала его номер телефона — $$$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$$$ строк.
54 812340219202156015678202212300678123456782 31341261231 4121012214 32510648599570544 779686369486033461422454541979482268
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» из первого номера телефона.
Название |
---|