Să considerăm o tablă de şah, formată din pătrate albe şi negre, plasate alternativ. Fiecare pătrat de pe tabla de şah are latura de L mm. Pătratul din colţul stânga-jos al tablei de şah este negru.
Vom considera un sistem cartezian de coordonate, cu originea plasată în colţul din stânga-jos al tablei. Astfel fiecare punct de pe tabla de şah poate fi identificat prin coordonatele sale carteziene (x, y), unitatea de măsură fiind mm.
Pe tabla de şah se află un greiere în punctul de coordonate (xg, yg). Greierele poate face salturi. La un salt el se va deplasa cu dx mm la dreapta şi dy mm în sus (adică din punctul de coordonate (x,y) va ajunge în punctul de coordonate (x+dx, y+dy)).

Cerinţă

Să se determine care este numărul minim de salturi pe care trebuie să le facă greierele până să ajungă în interiorul (nu şi pe bordura) unui pătrat de culoare albă (dacă acest lucru este posibil).

Date de intrare

Fişierul de intrare greiere.in conţine mai multe seturi de date de test, câte un set pe o linie. Un set de date de test constă din 5 numere naturale separate prin spaţii L xg yg dx dy, cu semnificaţia din enunţ. Fişierul se termină cu o linie pe care sunt scrise 5 valori 0 (acesta este ultimul set de date de test).

Date de ieşire

Fişierul de ieşire greiere.out va conţine câte o linie pentru fiecare set de date de test. Pe linia i va fi scris numărul minim de salturi pe care trebuie să le facă greierele până ajunge într-un pătrat alb pentru setul de date de pe linia i a fişierului de intrare. Dacă pentru setul de date respectiv nu există soluţie, în fişierul de ieşire se va scrie valoarea -1.

Restricţii

• 0 <= L <= 1000
• 0 <= xg, yg <= 100000
• 0 <= dx, dy <= 2000
• În fişierul de intrare există cel mult 100 de seturi de date de test.
• Pentru setul de date 0 0 0 0 0 se va afişa în fişierul de iesire 0.

Exemple

greiere.in	greiere.out
20 4 3 3 2 25 0 0 5 25 4 1 1 2 3 0 0 0 0 0	6 -1 3 0

prof. Emanuela Cerchez

Colegiul Naţional "Emil Racoviţă" Iaşi

emanuela.cerchez@gmail.com