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.

Cerinţă

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 comoara.in 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 comoara.out 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 și precizări

• $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 parţiale

Exemplu

comoara.in

3 5 8
4 

comoara.out

6
3 2
2 3
1 3
2 3
3 2
2 1

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$.