У мові програмуванея ЛІСП все пишеться у збалансованих дужках (ЯК ТУТ). А це значить, що ЛІСП-код іноді містить довгі відрізки закриваючих дужок ")))...)". Це буває дуже втомливо для ЛІСП-програміста, коли потрібно отримати таку кількість закриваючих дужок ')', яка у точності відповідає кількості відкритих дужок '('.
Щоб уникнути можливих у таких випадках помилок синтаксису, у деяких ділектах мови ЛІСП ввели магічну закриваючу дужку ']', яка замінює одну або декілька закриваючих дужок ')' для збалансування усіх раніше використаних відкриваючих дужок '('. Але тоді компілятор ЛІСП повинен вміти підраховувати скільки закриваючих дужок ')' кожна магічна дужка ']' дійсно замінила. Як?
Напишіть програму, яка отримує рядок, який складається з відкриваючих, закриваючих та магічних дужок, і яка підраховує для кожного входження магічної дужки якій кількості відкритих дужок вона відповідає. У випадку наявності декількох розв'язків програма повинна вивести один з них.
Первая строка содержит два целых числа 0 ≤ N ≤ 10000000 и 0 ≤ M ≤ 5000000 разделённых пробелом. Первое число N - это длина входной строки. Второе число M - это количество магических закрывающих скобок в строке. Оставшаяся часть входного файла начинаается во второй строке и содержит информацию о строке длины N и состоит из симовлов '(', ')' и ']'. Сивол ']' входит именно M ≤ N раз в эту строку. Эта строка разбита на подстроки длиной не более 72 символов для удобства чтения.
Первая строка содержит число 0' или '1'. Число '0' обозначает, что входные данные не могут быть сбалансированы (например, строка, состоящая из одной единственной закрывающей магической скобки "]" очевидно, что не может быть сбалансирована). В этом случае больше ничего не выводится.
Число '1' означает, что входные данные могут быть сбалансированы. В этом случае в выходных данных содержится M дополнительных строк.
Первая допополнительная строка содердит число C_1 ≥ 1 показывающее, сколько закрывающих скобок ')' заменяет 1-я магическая скобка ']' во входных данных. 2-я дополнительная строка содержит соответствующее число C_2 ≥ 1 для 2-й магической закрывающей скобки ']' во входных данныхз и т.д..
Если есть много способов, которыми данная строка может быть сбалансирована, ваша программа должна вывести один из них.
Пример входных данных описывает строку из 8 симовлов, из которыз 2 магические. Выходные данные содержат один из способов балансировки этой входной строки: первая магическая скобка соответствует 3-м открываюзщим скобкам, а вторая - 1-й открывающей скобке. И действительно в этом случае строка ( ( ((( ))) ) ) является правильно сбалансированной, и закрывающие скобки соответствуют нужному количеству закрывающих скобок, соответсвующие закрывающие символы подчёркнуты.