Fişierul intrare/ieşire:	comoara.in, comoara.out	Sursă	Lot Alba Iulia 2004
Autor	Marius Andrei	Adăugată de	Constantin-Buliga Stefan •fanache99
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Comoara

Până acum, pentru a găsi o comoară, un căutător trebuia sa treacă de diferite teste: trebuie să scape de bolovani uriaşi, de balauri, de săgeţi otrăvite. Comoara din insula piraţilor este mai specială, deoarece căpitanul care a ascuns-o a dorit să se asigure ca doar cineva care este perspicace va reuşi să ajungă la ea. Astfel, el a introdus o ultimă probă de perspicacitate, care se găseşte chiar în faţa intrării la comoară. Această ultimă probă este proba vaselor.
Căutătorii au la dispoziţie trei vase. Vasul 1 are capacitatea A, vasul 2 are capacitatea B, iar vasul 3 are capacitatea C. Capacităţile celor vase îndeplinesc relaţiile: A<B<C şi A+B=C.
La începutul probei, C este întotdeauna plin, iar A şi B goale. Pentru a trece cu succes de această probă şi a ajunge la comoară, căutătorii trebuie să facă în aşa fel încât să rămână în oricare dintre vase M litri de apă.
Pentru aceasta ei pot efectua una sau mai multe mutări. O mutare din vasul x în vasul y constă din turnarea conţinutului vasului x în vasul y până când vasul x se goleşte sau vasul y se umple.

Ajutaţi căutătorii de comori să treacă de ultima probă şi ei vă vor da o parte din comoara găsită.

Date de intrare

Fişierul de intrare are două linii. Pe prima linie se află 3 numere naturale separate prin câte un spaţu A B C, având semnificaţia din enunţ. Pe a doua linie se găseşte un număr natural M reprezentând numărul de litri de apă ce trebuie să rămână într-un vas pentru a trece proba.

Date de ieşire

Fişierul de ieşire va conţine pe prima linie un număr natural N, reprezentând numărul de mutări efectuate.
Pe următoarele N linii vor fi descrise cele N mutări, câte o mutare pe o linie. O mutare va fi descrisă ca o pereche x y de numere distincte din mulţimea {1, 2, 3}, cu semnificaţia « se toarnă apă din vasul x în vasul y ».

Restricţii

• 0 < A, B, C < 100 001
• numărul de mutări nu trebuie să fie minim însă el nu trebuie să depăşească 200 000
• testele folosite vor avea soluţie
• nu se acord punctaje partiale

Exemplu

Explicaţie

În cele 3 vase rămân următoarele cantităţi:
0 5 3
3 2 3
0 2 6
2 0 6
2 5 1
3 4 1

Cum se trimit solutii?