Iekavu pievienošana

Uzdevums

Aplūkosim virknes, kas veidotas tikai no apaļajām un kvadrātiekavām, t.i., simboliem '()[]'.

Korektu iekavu izteiksmi definē šādi:

• () un [] ir korektas iekavu izteiksmes;
• ja A ir korekta iekavu izteiksme, tad (A) un [A] arī ir korektas iekavu izteiksmes;
• ja A un B ir korektas iekavu izteiksmes, tad AB arī ir korekta iekavu izteiksme.

Piemēram, virknes '()()[]', '([])[()]' un '[(())][]' ir korektas iekavu izteiksmes, bet '(', '][', '([)]' nav.

Par derīgu virknes fragmentu sauksim pēc kārtas sekojošus virknes simbolus, ja tie veido korektu iekavu izteiksmi.

Jums ir dota iekavu virkne. Katrā solī virknes sākumā vai beigās tiek pievienota viena iekava (apaļā vai kvadrātiekava, atverošā vai aizverošā).

Uzrakstiet programmu, kas pēc katra soļa nosaka īsākā derīgā virknes fragmenta, kas satur šajā solī pievienoto iekavu, garumu!

Ievaddati

Teksta faila iekavas5.dat pirmajā rindā dota sākotnējā iekavu virkne. Tās garums nepārsniedz 100,000.

Nākamajā rindā dots vesels skaitlis N, 1 ≤ N ≤ 100,000, - soļu skaits.

Katrā no nākamajām N rindām dots vesels skaitlis A un simbols C (starp tiem ir tukšumsimbols). Ja A ir nulle (0), tad simbols C tiek pievienots virknes sākumā, bet, ja A ir viens (1), tad C tiek pievienots virknes beigās.

Izvaddati

Teksta faila iekavas5.rez katrā no N rindām jāizvada prasītā fragmenta garums pēc kārtējā soļa izpildes. Ja tāda fragmenta nav, jāizvada skaitlis 0.

Piemērs

iekavas5.dat	iekavas5.rez
( 1 1 )	2
iekavas5.dat	iekavas5.rez
(] 3 1 ] 0 ) 0 (	0 0 2
iekavas5.dat	iekavas5.rez
[]) 3 0 ) 0 ( 0 (	0 2 6

Atsauces