Šeštadieninė informatikos olimpiadininkų mokykla

Failų sąraše rinkdamasis failus Vilius pastebėjo, jog tą patį failų rinkinį gali pažymėti keliais būdais. Paprastu spragtelėjimu pele jis gali pažymėti vieną failą (ankstesni žymėjimai atšaukiami). Spragtelėjimas nuspaudus „Shift“ klavišą pažymi visą failų sritį tarp prieš tai ir dabar nuspaustų failų imtinai (ankstesni žymėjimai atšaukiami). Galiausiai, spragtelėjimas nuspaudus „Ctrl“ klavišą pakeičia vieno failo būseną (jei jis buvo pažymėtas, tampa nepažymėtu, ir atvirkščiai).

Pavyzdžiui, iš pradžių spragtelime ant failo Nr. 4 – tada pažymėtas failas Nr. 4. Nuspaudus „Shift“ klavišą spragtelime ant failo Nr. 8 – tada pažymėti failai Nr. 4, 5, 6, 7 ir 8. Nuspaudus „Ctrl“ klavišą spragtelime ant 5 – tada pažymėti failai Nr. 4, 6, 7, 8. Nuspaudus „Ctrl“ klavišą spragtelime failą Nr. 10 – tada pažymėti failai Nr. 4, 6, 7, 8 ir 10. Nuspaudus „Shift“ klavišą spragtelime failą Nr. 8 – tada pažymėti failai Nr. 8, 9 ir 10.

Vilius norėtų sužinoti, kiek mažiausiai spragtelėjimų pele prireiktų norint pasiekti tam tikrą pažymėjimą – parašykite programą, kuri padėtų jam tai sužinoti.

Pradiniai duomenys

Pirmoje eilutėje yra failų kiekis . Antroje eilutėje yra simbolių „*“ arba „.“, žyminčių Viliaus norimą pažymėjimą. Jei -asis simbolis yra „*“, vadinasi -asis failas turi būti pažymėtas, o jei „.“ – turi būti nepažymėtas.

Rezultatai

Pirmoje eilutėje išveskite sveikąjį skaičių – kiek mažiausiai spragtelėjimų pele reikia atlikti norint pasiekti duotą būseną. Tolesnėse eilučių pateikite failų numerius jų spragtelėjimo eilės tvarka, po vieną eilutėje. Jei spragtelima nuspaudus kurį nors iš klavišų, prieš skaičių prirašykite atitinkamai „Shift+“ arba „Ctrl+“.

Jei yra keli sprendiniai, išveskite bet kurį.

Pavyzdžiai

10
.*..**.**.

4
5
Shift+9
Ctrl+7
Ctrl+2

10
.*..**..**

5
2
Ctrl+5
Ctrl+6
Ctrl+9
Ctrl+10