Дано n строк s1, s2, ..., sn, состоящих из символов 0 и 1. Далее m раз создается новая строка как конкатенация уже имеющихся. Формально, на i-м шаге конкатенация saisbi записывается в новую строку sn + i (нумерация шагов ведется с 1). После каждой операции вам нужно найти максимальное положительное целое число k такое, что в полученной строке встречаются все возможные строки из 0 и 1 длины k (а таких различных строк 2k) как подстроки. Если такого k не существует, выведите 0.
Выходные данные
Выведите m строк, содержащие по одному целому числу — ответы на запросы после операций.
Примечание
В первой операции создается строка "0110". Для k = 1 две возможные бинарные строки длины k — это "0" и "1", они обе являются подстроками новой строки. Для k = 2 и больше существуют строки длины k, не встречающиеся в получившейся строке (для k = 2 такая строка — это "00"). Поэтому ответ равен 1.
Во второй операции создается строка "01100". Теперь присутствуют все строки длины k = 2.
В третьей операции создается строка "1111111111". В ней нет нулей, поэтому ответ равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
01
10
101
11111
0
3
1 2
6 5
4 4
|
1
2
0
|