Sehrli mötərizələr

Proqramlaşdırma dili LISP-də hər şey balanslaşdırılmış mötərizələrdə yazılır (BUNUN KİMİ). Bu, LISP kodunun bəzən uzun bağlayıcı mötərizə ardıcıllıqları ")))...)" ehtiva etməsi deməkdir. Bu, LISP proqramçısı üçün yorucu ola bilər, çünki açıq mötərizələrin '(' sayına tam uyğun gələn bağlayıcı mötərizələrin ')' sayını təmin etmək lazımdır.

Belə hallarda mümkün sintaksis səhvlərinin qarşısını almaq üçün, LISP dilinin bəzi dialektlərində sehrli bağlayıcı mötərizə ']' təqdim edilmişdir. Bu, əvvəl istifadə edilmiş açıq mötərizələrin '(' hamısını balanslaşdırmaq üçün bir və ya bir neçə bağlayıcı mötərizəni ')' əvəz edir. Lakin, bu halda LISP kompilyatoru hər sehrli mötərizənin ']' əslində neçə bağlayıcı mötərizəni ')' əvəz etdiyini hesablamağı bacarmalıdır. Necə?

Bir proqram yazın ki, açıq, bağlayıcı və sehrli mötərizələrdən ibarət olan bir sətir alsın və hər sehrli mötərizənin neçə açıq mötərizəyə uyğun gəldiyini hesablasın. Bir neçə həll yolu varsa, proqram onlardan birini çıxarmalıdır.

Giriş verilənləri

Birinci sətir boşluqla ayrılmış iki tam ədəd 0 ≤ N ≤ 10000000 və 0 ≤ M ≤ 5000000 ehtiva edir. Birinci ədəd N - giriş sətirinin uzunluğudur. İkinci ədəd M - sətirdəki sehrli bağlayıcı mötərizələrin sayıdır. Giriş faylının qalan hissəsi ikinci sətirdən başlayır və uzunluğu N olan sətir haqqında məlumat ehtiva edir və '(', ')' və ']' simvollarından ibarətdir. ']' simvolu bu sətirdə dəqiq M ≤ N dəfə iştirak edir. Bu sətir oxumaq rahatlığı üçün uzunluğu ən çox 72 simvol olan alt sətirlərə bölünmüşdür.

Çıxış verilənləri

Birinci sətir '0' və ya '1' ədədini ehtiva edir. '0' ədədi giriş məlumatlarının balanslaşdırıla bilməyəcəyini göstərir (məsələn, yalnız bir sehrli bağlayıcı mötərizədən "]" ibarət olan sətir açıq-aşkar balanslaşdırıla bilməz). Bu halda başqa heç nə çıxarılmır.

'1' ədədi giriş məlumatlarının balanslaşdırıla biləcəyini göstərir. Bu halda çıxış məlumatlarında M əlavə sətir var.

Birinci əlavə sətir giriş məlumatlarındakı 1-ci sehrli mötərizənin ']' neçə bağlayıcı mötərizəni ')' əvəz etdiyini göstərən C_1 ≥ 1 ədədini ehtiva edir. 2-ci əlavə sətir giriş məlumatlarındakı 2-ci sehrli bağlayıcı mötərizənin ']' üçün müvafiq C_2 ≥ 1 ədədini ehtiva edir və s.

Əgər bu sətirin balanslaşdırıla biləcəyi bir çox yol varsa, proqramınız onlardan birini çıxarmalıdır.

Nümunələr

Qeyd

Giriş məlumatlarının nümunəsi 8 simvoldan ibarət olan və bunlardan 2 sehrli olan bir sətiri təsvir edir. Çıxış məlumatları bu giriş sətirini balanslaşdırma yollarından birini ehtiva edir: birinci sehrli mötərizə 3 açıq mötərizəyə, ikincisi isə 1 açıq mötərizəyə uyğundur. Həqiqətən bu halda sətir ( ( ((( ))) ) ) düzgün balanslaşdırılmışdır və bağlayıcı mötərizələr lazım olan bağlayıcı mötərizələrin sayına uyğundur, uyğun bağlayıcı simvollar vurğulanmışdır.