Statement is not available in English language
C. Телепортация в Немалополисе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно в Немалополисе разработали инновационный метод телепортации. Для повышения комфорта жителей в городе было установлено $$$n$$$ телепортов, пронумерованных от $$$1$$$ до $$$n$$$.

Учёные-немалисты рассчитали ограничения, которые обеспечат безопасность телепортационной сети. Для каждого телепорта было выписано слово $$$s_i$$$ соответственно. За $$$|s_i|$$$ они обозначили длину строки $$$i$$$. Также они выбрали целое число $$$k$$$. Учёные разрешили горожанам телепортироваться из телепорта $$$i$$$ в телепорт $$$j$$$ при условии, что пассажир предъявит такое число $$$m$$$, что:

  • суффикс $$$s_i$$$ длины $$$m$$$ равен префиксу $$$s_j$$$ длины $$$m$$$;
  • суффикс $$$s_i$$$ длины $$$m + 1$$$ не равен префиксу $$$s_j$$$ длины $$$m + 1$$$ (в частности, если $$$m + 1 \gt \min(|s_i|, |s_j|)$$$);
  • $$$k \le m \leq \min(|s_i|, |s_j|)$$$ (по Федеральному Закону «О немалости операций»).

При этом стоимость такой телепортации составляет $$$m$$$ немалей (местная валюта).

Например, для $$$s_i =$$$ «abcde» и $$$s_j =$$$ «cdef» подходит только $$$m = 3$$$, и стоить такая телепортация будет $$$3$$$ немаля.

Мэр города, Немалуй, собирает сведения об эффективности телепортов. Для каждого телепорта $$$i$$$ ($$$2 \le i \le n$$$) вам нужно найти минимальное число немалей, необходимое для того, чтобы добраться от $$$1$$$-го телепорта до телепорта $$$i$$$, совершив какое-то количество телепортаций.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее идут описания наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) и $$$k$$$ ($$$1 \le k \le 3 \cdot 10^5$$$) — количество телепортов и ограничение на стоимость телепортации соответственно.

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

Гарантируется, что сумма $$$|s_i|$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных в отдельной строке выведите $$$n - 1$$$ число — стоимости проезда от телепорта $$$1$$$ до телепортов $$$2, 3, 4, \dots, n$$$ соответственно. Если до какого-то телепорта никак нельзя доехать, выведите вместо стоимости проезда до него число $$$-1$$$.

Пример
Входные данные
5
5 1
skolko
nemalo
kolba
zamkadom
aramzamzam
4 2
arbuzik
ikra
pupupu
kokos
2 1
uwuuu
uuuwu
2 1
uuuuu
uuuuu
4 7
extraordinarilymagnificentunbelievablilityoverenthusiasticallyhyperactive
overenthusiasticallyhyperactiveperpetualmotionunintentionallymisunderstood
unintentionallymisunderstoodhilariousscenariofantasticallyextraordinari
fantasticallyextraordinarilybizarreadventure
Выходные данные
-1 2 6 3 
2 -1 -1 
3 
5 
31 59 85
Примечание

В первом наборе входных данных мы можем телепортироваться: «skolko» $$$\overset{2}{\to}$$$ «kolba» $$$\overset{1}{\to}$$$ «aramzamzam» $$$\overset{3}{\to}$$$ «zamkadom».

Во втором наборе входных данных мы не можем попасть из «arbuzik» в «kokos», так как проезд между ними стоит $$$1$$$, что меньше $$$k = 2$$$.

В третьем наборе входных данных мы не можем попасть из «uwuuu» в «uuuwu», предъявив $$$m = 1$$$ или $$$m = 2$$$, так как условие на то, что суффикс $$$s_i$$$ длины $$$m + 1$$$ не совпадает с префиксом $$$s_j$$$ длины $$$m + 1$$$, не выполнено.

В четвёртом наборе входных данных мы можем попасть из «uuuuu» в «uuuuu» только при $$$m = 5$$$, так как при меньших условие на $$$m + 1$$$ не выполнено.

Пятый набор входных данных настолько немалый, что его мы комментировать не будем.