Zadanie

Izbové monštrum

Počet bodov: 60, časový limit: 500ms

Dávid sa z nudy začal prehrabávať v hŕbe starých súčiastok, televízorov, kalkulačiek, procesorov, … a čo nevidieť, mal zostrojený hračkársky počítač. Nazval ho “Izbové monštrum”.

Dávidov počítač funguje nasledovne. Pracuje primárne s dvojicami čísel, a vie s nimi robiť niekoľko rôznych operácii, ktoré popíšeme neskôr. Pamäť počítača je indexovaná prirodzenými číslami, pričom na začiatku je na indexe \(0\) hodnota \((x, y)\) a ostatné pamäťové miesta sú voľné. Je chyba, keď pri výpočte používame hodnotu na voľnom pamäťovom mieste.

Podporované operácie sú tri. Každá vezme hodnoty z niekoľkých pamäťových miest, prípadné číselné argumenty, spracuje ich, a výsledok uloží na prvé voľné pamäťové miesto. Operácie sú:
- Zoberie hodnotu \((a, b)\), kladné číslo \(l\) a vráti \((a+l, b+l)\).
- Zoberie hodnotu \((a, b)\), kde \(a\) aj \(b\) sú párne. Vráti \((\frac{a}{2}, \frac{b}{2})\).
- Zoberie dve (nie nutne rôzne) hodnoty \((a, b)\) a \((c, d)\), ktoré spĺňajú \(b = c\). Vráti \((a, d)\).

Dávida teraz zaujíma, či vie nejakou postupnosťou operácii získať hodnotu \((x', y')\). Hľadá teda takú postupnosť operácii, po ktorej bude v poslednom použitom pamäťovom mieste hodnota \((x', y')\).

Vstup a výstup

Vstup bude pozostávať s viacerých testovacích prípadov. Na prvom riadku je číslo \(t\), určujúce ich počet. Nasledujú popisy jednotlivých prípadov, každý z nich na samostatnom riadku. Vo všetkých vstupoch okrem vzorového platí \(t = 100\).

Popis prípadu obsahuje štyri kladné celé čísla oddelené medzerou: \(x, y, x'\) a \(y'\). Prvé dve určujú hodnotu na pamäťovom mieste \(0\), s ktorou Dávid začína. Ďalšie dve určujú cieľovú hodnotu, ktorú chce Dávid dosiahnuť. Tieto štyri čísla neprevýšia \(10^9\).

Ak sa cieľová hodnota nedá dosiahnuť, vypíšte riadok obsahujúci číslo \(-1\). Ak sa dá dosiahnuť, vypíšte v prvom riadku počet operácii, ktoré použijete. Potom vypíšte popisy jednotlivých operácii, každý na samostatnom riadku. Popis každej operácie začína typom operácie (\(1\), \(2\) alebo \(3\)), nasledujú čísla pamäťových miest, ktoré sú argumentami pre tú operáciu (môžu byť aj rovnaké), a potom prípadné číselné argumenty. Všetky čísla v popise operácie sú oddelené medzerami.

Medzi každými dvoma odpoveďami (na jednotlivé testovacie prípady) nech je prázdny riadok.

Ak existuje viacero správnych postupností operácii, smiete vypísať ľubovoľnú z nich. Nemusí byť najkratšia, musíte ju ale stihnúť vypísať v časovom limite.

Príklad

Input:

2
1 1 2 3
3 5 100 101

Output:

-1

3
1 0 1
2 1
1 0 98

V druhom prípade by sme vedeli dosiahnuť cieľové hodnoty aj na \(2\) operácie.