Наша компанія поповнилась ще двома прихильниками пригод: Леонідом та Оленою. За декілька годин вони прибудуть на фестиваль Червоного Капелюха. Проте, Льоня згадав про основне правило Кості: «розберемося на місці». Тому він вирішив завчасно перевірити наші білети на фестиваль.
Узявши всі чотири білети, він почав розбиратися в структурі номеру. За правилами, вона має бути наступною:
Правильна дужкова послідовність (ПДП) — окремий випадок дужкової послідовності. Правильні дужкові послідовності формально визначаються таким чином:
Правила дуже прості, однак довжина номеру може бути до 106 символів. Ніхто з учасників поїздки не бажає рахувати це вручну, а я пишу цю задачу й сиджу за кермом. Тому, Льоня простить вас перевірити правильність номерів.
Програма читає зі стандартного пристрою введення одне ціле число N (0 < N < 106) - довжину номера білету. В наступних чотирьох рядках знаходиться N символів (цифри або дужки) - номери білетів кожного з учасників фестивалю.
Програма виводить на пристрій стандартного виведення чотири слова (по одному у рядку):
5 1[{}] 1{10} 8(22) {101}
PROBLEM TWO ONE PREMIUM