Šeštadieninė informatikos olimpiadininkų mokykla

Du broliai, Kairys ir Dešinys, labai mėgsta skaityti knygas. Deja, jų knygų lentyna dabar yra tuščia (nes senoji sulūžo nuo per didelio knygų svorio, tad teko įsigyti naują). Kairys ir Dešinys nebūtų Kairys ir Dešinys jei nepradėtų kaipmat pildyti knygų lentynos naujomis knygomis. Tiesa, broliai su knygomis elgiasi savotiškai - Kairys knygas deda į lentyną ir ima iš lentynos visada iš kairės pusės, o Dešinys - iš dešinės.

Broliai sutarė, kokia tvarka atliks pakeitimus knygų lentynoje, o savo sutarimą užsirašė sąraše. Kiekviena sąrašo eilutė yra vieno iš keturių tipų:

• - Kairys padeda knygą su numeriu į lentyną;
• - Dešinys padeda knygą su numeriu į lentyną;
• - Kairys paima knygą iš lentynos ir ją skaito;
• - Dešinys paima knygą iš lentynos ir ją skaito.

Be abejo, abu broliai yra nekantrūs ir nori kuo greičiau sužinoti, kokias knygas gaus paskaityti, nors dar net nepradėjo vykdyti savo sąraše surašytų veiksmų. Parašykite programą, kuri išanalizuotų brolių sąrašą ir nustatytų, kokias knygas ir kokia eilės tvarka broliai gaus perskaityti.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius - sąrašo įrašų kiekis ().

Toliau seka eilučių. Kiekvienoje iš jų aprašyta po vieną taisyklę pagal sąlygoje pateiktą formatą. Visų knygų numeriai yra tarp ir .

Rezultatai

Kiekvienai tipo taisyklei jūsų programa turi išvesti po vieną eilutę su vienu sveikuoju skaičiumi - knygos, kurią kažkuris iš brolių dabar gaus perskaityti, numerį.

Pavyzdžiai

8
1 K 1
1 K 2
2 D
1 D 3
2 K
1 D 4
2 K
2 D

1
2
3
4

Paaiškinimas

Knygų lentynos būseno po kiekvieno iš pavyzdyje aprašytų veiksmų:

1. 
2. 
3. (Dešinys paėmė skaityti 1)
4. 
5. (Kairys paėmė skaityti 2)
6. 
7. (Kairys paėmė skaityti 3)
8. (Kairys paėmė skaityti 4)