Суффиксный массив

Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если:

• все строки в множестве различны;
• не существует такой пары различных строк, что одна строка является суффиксом другой.

Строка s называется суффиксом строки t, если длина строки s не больше длины строки t, а также для любого i i-й символ строки s, считая с конца, совпадает с i-м символом строки t, считая с конца.

Например, ab является суффиксом строк ab и cab, но не является суффиксом строк a и ac.

Петя же решил придумать что-то новое и ввёл новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое что:

• все строки в множестве различны;
• у любых двух различных строк наибольший общий суффикс имеет длину не больше k.

Наибольшим общим суффиксом двух строк s и t называется наибольшая по длине строка, являющаяся суффиксом обеих строк.

Теперь по данному набору строк s1, s2, ..., sn и числу k Петя хочет найти в этом наборе k-бессуффиксный код, состоящий из максимально возможного количества строк.

Помогите ему — найдите этот код.
 

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

В первой строке содержатся два числа n и k — количество строк в наборе и максимальная длина общего суффикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100). В i-й из следующих n строк содержится строка si — i-е слово из набора (1 ≤ |si| ≤ 100). Все строки состоят из строчных латинских букв. Гарантируется, что суммарная длина всех строк не превосходит 106.
 

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

В первой строке выведите число m — максимально возможное количество строк в k-бессуффиксном коде. В следующих m строках выведите элементы этого кода. Элементы можно выводить в любом порядке. Если существует несколько ответов с максимальным m, разрешается вывести любой.

Примечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:

Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x₁,y) (x₂,y) (x₁≤x₂) есть часть подмножества, то все ячейки (x,y) с x₁≤x≤x₂ также часть подмножества.
Если ячейки (x,y₁) and (x,y₂) (y₁≤y₂) есть часть подмножества, то все ячейки (x,y) with y₁≤y≤y₂ также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 10⁹+7.

Входные данные: 
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.

Выходные данные: 
Количество сбалансированных подмножеств по модулю 10⁹+7.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 GG GG	13	Для этого теста все 4-связные подмножества сбалансированные. G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2	4 GGGG GGGG GG.G GGGG		642 Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию: GG.. .G.. GG.. ....