Магічні дужки
Мова програмування ЛІСП вся пишеться в збалансованих дужках (ЯК ЦЕ). Це означає, що ЛІСП-код іноді містить довгі послідовності закриваючих дужок ")))...)". Це може бути досить втомливо для ЛІСП-програміста, коли потрібно забезпечити, щоб кількість закриваючих дужок ')' точно відповідала кількості відкриваючих дужок '('.
Щоб уникнути можливих синтаксичних помилок у таких випадках, деякі діалекти мови ЛІСП ввели магічну закриваючу дужку ']', яка замінює одну або кілька закриваючих дужок ')' для збалансування всіх раніше використаних відкриваючих дужок '('. Але тоді компілятор ЛІСП повинен вміти підраховувати, скільки закриваючих дужок ')' кожна магічна дужка ']' дійсно замінила. Як це зробити?
Напишіть програму, яка отримує рядок, що складається з відкриваючих, закриваючих і магічних дужок, і підраховує для кожного входження магічної дужки, якій кількості відкритих дужок вона відповідає. У разі наявності кількох рішень програма повинна вивести одне з них.
Вхідні дані
Перша рядок містить два цілі числа 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-й відкриваючій дужці. І дійсно, в цьому випадку рядок ( ( ((( ))) ) ) є правильно збалансованим, і закриваючі дужки відповідають потрібній кількості закриваючих дужок, відповідні закриваючі символи підкреслені.