Маша познакомилась с новым другом и узнала его номер телефона — \(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\) запросов. В первой строке ответа должно содержаться одно число \(k\), соответствующее количеству отрезков, на которые вы разбили номер телефона \(s\). Выведите -1, если такого разбиения получить нельзя.
В случае положительного ответа далее должны следовать \(k\) строк, содержащие тройки чисел \(l, r, i\). Такая тройка обозначает, что очередные \(r-l+1\) цифр номера \(s\) равны отрезку (подстроке) с границами \([l, r]\) телефона под номером \(i\). И телефоны и цифры в них нумеруются от \(1\). Обратите внимание, что \(r-l+1 \ge 2\) для всех \(k\) строк.
Примечание
Первый тестовый случай соответствует примеру из условия.
Во втором случае невозможно представить отрезками известных номеров длины 2 или более.
В третьем случае можно получить отрезки «12» и «21» из первого номера телефона.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|