Задача 05D. Вывод сжатого суффиксного дерева ≡

Условие

Сжатое суффиксное дерево, построенное по алгоритму Укконена, в каждом своем ребре хранит информацию о символах которые там находятся, а именно (первый символ, глубина*, индекс первого символа ребра, индекс последнего символа ребра)

Требуется найти все ребра, находящееся на глубине D.

Вывод требуется выполнять по аналогии с алгоритмом поиск в глубину, то есть вывод выполняется из корня к листьям

Формат входных данных

Входной файл содержит строку длины D из которой было построено дерево и глубину l

Формат выходных данных

Программа должна вывести поочередно все ребра с их параметрами. Каждое ребро записывается с новой строки, все индексы берутся из соответствующих символов в исходной строке.

Алгоритм Укконена подразумевает наличие конечного символа в строке, но в данной задаче при выводе ребер этот символ не должен встречаться

*Глубина - расстояние ребра от корня дерева (изначально равна 0).

Ограничения

0 ≤ S ≤ 100000

1 ≤ D ≤ 5

Примеры тестов

abcd 1

$ 1 4 4
a 1 0 4
b 1 1 4
c 1 2 4
d 1 3 4

abcabxabcd 2

c 2 2 2
x 2 5 10
c 2 2 2
x 2 5 10
a 2 3 10
d 2 9 10