Постройте суффиксное дерево для заданной строки s.
Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100 000). Строка состоит из строчных латинских букв.
В первой строке выходного файла выведите два натуральных числа n и m, разделенных пробелом — число вершин и ребер в суффиксном дереве соответственно. В следующих m строках выведите описания ребер в формате <родитель> <потомок> <l> <r>. Эта запись означает, что на ребре написана строка s[l..r], при этом значение l должно быть минимально возможным. Корнем дерева должна быть вершина с номером 1. Вершины должны быть занумерованы натуральными числами, не превышающими n.
ababb
7 6
1 4 1 2
1 6 2 2
4 2 3 5
4 5 5 5
6 3 3 5
6 7 5 5
Очень известный автор не менее известной книги решил написать продолжение своего произведения. Он писал все свои книги на компьютере, подключенном к интернету. Из-за такой неосторожности мальчику Ненокку удалось получить доступ к еще ненаписанной книге. Каждый вечер мальчик залазил на компьютер писателя и записывал на свой компьютер новые записи. Ненокку, записав на свой компьютер очередную главу, заинтересовался, а использовал ли хоть раз писатель слово "книга". Но он не любит читать книги (он лучше полазает в интернете), и поэтому он просит вас узнать есть ли то или иное слово в тексте произведения. Но естественно его интересует не только одно слово, а достаточно много.
В каждой строчке входного файла записано одна из двух записей.
1 означает просьбу проверить существование подстроки <слово> в произведение.
2 означает добавление в произведение <текст>.
Писатель только начал работать над произведением, поэтому он не мог написать более 105 символов. А входной файл содержит не более 15 мегабайт информации.
Выведите на каждую строчку типа 1 "YES", если существует подстрока <слово>, и "NO" в противном случае. Не следует различать регистр букв.
? love
? is
A Loveis
? love
? WHO
A Whoareyou
? is
NO
NO
YES
NO
YES