Consideram o tabla de sah infinita. O pozitie pe
tabla de sah (un patratel) este identificata prin coordonatele sale,
doua numere intregi x si y,
reprezentand linia respectiv coloana pe care se afla patratelul respectiv.
Patratul de coordonate (0,0) este undeva
in centrul acestei table infinite, astfel ca pozitiile de pe tabla de
sah pot avea atat coordonate pozitive, cat si coordonate negative.
Pe aceasta tabla de sah se afla N cai speciali.
Un cal special face salturi in forma literei L
(ca si un cal obisnuit), doar ca dimensiunea literei este diferita.
Mai exact, la un salt, un cal special aflat in pozitia (x,y)
se poate deplasa in una dintre urmatoarele 8 pozitii: (x-p,
y-q), (x-p, y+q), (x+p,y-q), (x+p,y+q), (x-q,y-p), (x-q, y+p), (x+q,y-p),(x+q,y+p).
De exemplu, daca un cal special se afla pozitia (0,0),
iar p=2, q=4,
atunci poate sari intr-una dintre pozitiile (-4,-2),
(-4,2), (-2,-4), (-2,4), (2,-4), (2,4), (4,-2), (4,2).
Cerinţă
Determinati numarul cailor care prin sarituri
succesive pot ajunge din pozitia lor initiala in patratul de coordonate
(0,0).
Date de intrare
Fisierul de intrare cai.in
contine pe prima linie numerele naturale N,
p si q,
separate prin cate un spatiu. Pe fiecare dintre urmatoarele N
linii se afla cate doua numere naturale x,
y separate
printr-un spatiu, reprezentand pozitiile initiale ale fiecarui cal.
Date de ieşire
Fisierul de iesire cai.out
va conţine o singură linie pe care va fi scris un singur număr natural,
reprezentând numarul cailor care pot ajunge prin salturi succesive in
patratul (0,0).
Restricţii
3 <= N <= 30 000
1 <= p, q <= 100
x si y
sunt numere naturale strict pozitive de cel mult 50 de cifre
Pe tabla de sah pot fi oricati cai in aceeasi
pozitie, in orice moment
Exemple
cai.in
cai.out
Explicaţii
5 2 4
3 1
4 8
12 12
1 1
4 2
3
Numai trei cai
dintre cei cinci pot ajunge in origine. Calul din pozitia (4,
8) sare mai intai in (2,
4), apoi in (0,0).
Traseul nu e unic.
Calul din (12,12)
sare in (10, 8),
(6,6),
(2,4),
(0,0)
Calul din (4,2)
sare direct in (0,0).
Ceilalti doi cai nu pot ajunge in origine.
cai.in
cai.out
Explicaţii
3 1 2
3 1
2 2
4 3
3
Toti cei trei
cai pot ajunge in origine: (3,1) -> (1,2) -> (0,0)
(2,2) -> (0,1) -> (2,0) -> (1,-2) -> (0,0)
(4,3) -> (3,1) -> (1,2) -> (0,0)