Магические скобки

Язык программирования ЛИСП всё пишется в сбалансированных скобках (КАК ЭТО). А это значит, что ЛИСП-код иногда содержит длинные отрезки закрывающих скобок ")))...)". Это бывает очень утомительно для ЛИСП-программиста, когда нужно получить такое количество закрывающих скобок ')', которое точно соответствует количеству открытых скобок '('.

Чтобы предотвратить возможные в таких случаях ошибки синтаксиса, в некоторых дилектах языка ЛИСП ввели магическую закрывающую скобку ']', которая заменяет одну или несколько закрывающих скобок ')' для сбалансирования всех ранее использованных открывающих скобок '('. Но тогда компилятор ЛИСП должен уметь подсчитывать сколько закрывающих скобок ')' каждая магическая скобка ']' действительно заменила. Как?

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

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

Первая строка содержит два целых числа 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-й открывающей скобке. И действительно в этом случае строка ( ( ((( ))) ) ) является правильно сбалансированной, и закрывающие скобки соответствуют нужному количеству закрывающих скобок, соответсвующие закрывающие символы подчёркнуты.