После второго тура Дольчик решил отпраздновать окончание респы. Было решено организовать After party.
После $$$5$$$ выпитых бутылок липтона из окна полетели зарядки, пиццы и т.д. На звуки громкой музыки пришел Александр, которому стало интересно, что тут происходит. Зайдя в комнату, он увидел немного пьяного Дольчика. Хоть тот и всё отрицал, но Александр что-то заподозрил. Поэтому он решил устроить ему проверку трезвости.
Александр дал Дольчику массив строк $$$s$$$ размером $$$n$$$ и целое число $$$k$$$. Рассмотрим множество всех таких непустых строк, которые встречаются как подстроки во всех строках массива $$$s$$$ одновременно. И Александр просит Дольчика найти $$$k$$$-ую в лексикографическом порядке строку из этого множества.
Первая строка содержит два целых числа $$$n, k$$$ ($$$2 \leq n \leq 3 \cdot 10^5, 1 \leq k \leq 10^{12}$$$) — длина массива $$$s$$$ и целое число $$$k$$$ соответственно.
Следующая строка содержит $$$n$$$ целых чисел $$$s_1,s_2,\dots,s_n$$$, разделенных пробелами — массив $$$s$$$.
Пусть $$$S$$$ — это суммарная длина всех $$$n$$$ строк массива $$$s$$$.
Тогда гарантируется, что $$$S$$$ не превосходит $$$3\cdot10^5$$$.
В первой строке выведите искомую строку или $$$-1$$$, если такой не существует.
| № | Дополнительные ограничения | Баллы за подзадачу | Необходимые подзадачи |
| $$$1$$$ | $$$S, n \leq 50$$$ | $$$5$$$ | |
| $$$2$$$ | $$$S, n \leq 700$$$ | $$$16$$$ | $$$1$$$ |
| $$$3$$$ | $$$n = 2, S \leq 5 \cdot 10^4$$$ | $$$19$$$ | |
| $$$4$$$ | $$$n = 2$$$ | $$$25$$$ | $$$3$$$ |
| $$$5$$$ | $$$S, n \leq 10^5$$$ | $$$11$$$ | $$$1$$$ — $$$3$$$ |
| $$$6$$$ | Нет дополнительных ограничений | $$$24$$$ | $$$1$$$ — $$$5$$$ |
2 3 aaa abaa
-1
2 2 aaa abaa
aa
