Pe malul unui râu se găseşte un pluton format din n soldaţi, numerotaţi de la 1 la n. Ei trebuie să traverseze râul, dar nu au la dispoziţie nici un mijloc de transport. Din fericire, chiar în dreptul lor, pe râu erau doi copii, Gigel şi Ionel, într-o mică barcă de cauciuc. Copiii au fost de acord să-i ajute pe soldaţi să traverseze râul, însă a apărut un mic inconvenient: în barcă, fiind mică, nu încape decât fie un singur soldat, fie cel mult cei doi copii. Ajutaţi-i pe Ionel şi Gigel să transporte întreg plutonul pe malul celălalt, iar ei să revină pe malul de pe care au plecat.
Cerinţă
Scrieţi un program care să afişeze o modalitate de utilizare a bărcii de cauciuc astfel încât la final toţi soldaţii să traverseze râul, realizând un număr minim de traversări.
Date de intrare
Fişierul de intrare barca.in are o singură linie pe care se găseşte numărul natural nenul n, reprezentând numărul de soldaţi din pluton.
Date de ieşire
Fişierul de ieşire barca.out va conţine pe prima linie numărul minim de traversări pe care le face barca pentru ca întreg plutonul să ajungă pe malul celălalt, iar ambii copii să revină pe maul de pe care au plecat. Urmează în fişîer atâtea linii câte traversări va efectua barca. Linia i+1 va conţine codificat conţinutul bărcii la traversarea i, şi anume:
- caracterul ′I′, dacă în barcă se găseşte doar Ionel
- caracterul ′G′, dacă în barcă se găseşte doar Gigel
- caracterele ′IG′ dacă în barcă se găsesc amândoi copiii
- un număr natural k, care reprezintă numărul de ordine al soldatului care este în barcă şi care traversează râul în acel moment.
Restricţii
1 ≤ n ≤ 35000
Iniţial barca şi cei doi copii se găsesc pe acelaşi mal cu soldaţii;
Când copiii se găsesc împreună pe acelaşi mal, Ionel are prioritate la folosirea bărcii;
Soldaţii vor traversa râul în ordinea numerotării lor;
După terminarea operaţiunii Ionel şi Gigel trebuie să rămână împreună pe acelaşi mal de unde au început traversarea.
Punctaj: Dacă numărul minim de traversări afişat este corect se obţine 20% din punctajul pe test. Punctajul integral se acordă dacă atât numărul minim de traversări, cât şi traversările sunt corecte.
Exemple
barca.in
barca.out
Explicaţii
1
4
IG
I
1
G
I şi G traversează râul împreună
I se întoarce pe malul cu soldaţi şi rămâne aici
soldatul 1 traversează râul şi rămâne acolo
G revine pe malul iniţial