Скобочной последовательностью называется строка, состоящая только из символов «(», «)», «[» и «]».
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()[]», «([])» — правильные (полученные выражения: «(1)+[1]», «([1+1]+1)»), а «](» и «[» — нет. Пустая строка является правильной скобочной последовательностью по определению.
Подстрокой s[l... r] (1 ≤ l ≤ r ≤ |s|) строки s = s1s2... s|s| (где |s| — длина строки s) называется строка slsl + 1... sr. Пустая подстрока по определению считается подстрокой любой строки.
Вам дана не обязательно правильная скобочная последовательность. Найдите ее подстроку, которая является правильной скобочной последовательностью и при этом содержит как можно больше скобок «[».
Выходные данные
В первой строке выведите единственное целое число — количество скобок «[» в оптимальной подстроке. Во второй строке выведите саму подстроку. Если существует несколько оптимальных подстрок выведите любую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
([])
|
1
([])
|
|
2
|
(((
|
0
|