Скобочной последовательностью называется строка, состоящая только из символов «(», «)», «[» и «]».

Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()[]», «([])» — правильные (полученные выражения: «(1)+[1]», «([1+1]+1)»), а «](» и «[» — нет. Пустая строка является правильной скобочной последовательностью по определению.

Подстрокой s[l... r] (1 ≤ l ≤ r ≤ |s|) строки s = s₁s₂... s_|s| (где |s| — длина строки s) называется строка s_ls_l + 1... s_r. Пустая подстрока по определению считается подстрокой любой строки.

Вам дана не обязательно правильная скобочная последовательность. Найдите ее подстроку, которая является правильной скобочной последовательностью и при этом содержит как можно больше скобок «[».