== include(page="template/taskheader" task_id="cypher") ==

Aceasta problema are dificultate medie

Tocmai aţi găsit cutia fermecată ce conţine 100 de puncte la o problemă de la testul practic. Totuşi, pentru a o putea deschide trebuie să spargeţi un cifru. Cifrul este construit ca un mecanism cu 4 discuri cu numere de la 0 la 9, sub fiecare disc aflându-se 2 butoane sub formă de săgeţi, fiecare buton deplasând discul de deasupra sa în ordinea indicată de săgeţi. Pentru o imagine mai clară asupra cum arată cifrul consultaţi poza de mai jos.

Tocmai aţi găsit cutia fermecată ce conţine 100 de puncte la o problemă de la testul practic. Totuşi, pentru a o putea deschide trebuie să spargeţi un cifru. Cifrul este construit ca un mecanism cu 4 discuri cu numere de la 0 la 9, deasupra fiecarui disc aflându-se 2 butoane sub formă de săgeţi, fiecare buton deplasând discul de deasupra sa în ordinea indicată de săgeţi. Pentru o imagine mai clară asupra cum arată cifrul consultaţi poza de mai jos.

!problema/cypher?image.jpg!

!problema/cypher?img5.jpg!
 
Fiecare configuraţie în care poate ajunge cifrul poate fi codificată printr-un număr pe 4 cifre. De exemplu starea din poză corespunde numărului 3886.

Fiecare configuraţie în care poate ajunge cifrul poate fi codificată printr-un număr pe 4 cifre. De exemplu starea din poză corespunde numărului 8056.

Pentru a obţine cele 100 de puncte voi trebuie să aduceţi cifrul dintr-o stare iniţială I ~1~ I ~2~ I ~3~ I ~4~ într-o stare finală F ~1~ F ~2~ F ~3~ F ~4~ printr-un număr minim de apăsări de buton, fără a trece printr-o configuraţie interzisă.

Pe prima linie se găseşte starea iniţială I ~1~ I ~2~ I ~3~ I ~4~, şi pe a 2-a linie starea finală F ~1~ F ~2~ F ~3~ F ~4~.
Pe a 3-a linie se găseşte numărul N reprezentând numărul de stări interzise, iar pe următoarele N linii se găsesc cate 4 numere R ~1~ R ~2~ R ~3~ R ~4~ reprezentând stările interzise.

*Hint*
Dacă o stare este reprezentată ca un număr de 4 cifre, pentru a trece la următoarea stare trebuie adunat sau scăzut la acesta o putere a lui 10. 6666 + {1, 10, 100, 1000}. Atenţie la overflow!
 

h2. Date de ieşire
Fişierul de ieşire $cypher.out$ va conţine T valori, fiecare pe câte o linie, reprezetând numărul minim de mutări pentru a ajunge din starea iniţială în starea finală în condiţiile precizate în enunţ, sau -1 în cazul în care acest lucru este imposibil.