Oglinzi Fermecate

Alex şi Lorena se află pe o linie infinită. Pe linie se află oglinzi fixe, fiecare la o poziţie exprimată printr-un număr întreg. În fiecare pas amândoi aleg câte o oglindă (aceiași sau diferită) şi se oglindesc simultan: dacă o persoană se află în poziţia $x$ şi se oglindeşte în oglinda aflată la poziţia $y$, atunci noua poziţie va fi $z=2y-x$. Cu alte cuvinte, $z$ este simetricul lui $x$ faţă de $y$. Fiind suflete pereche, Alex și Lorena își doresc să ajungă pe aceeași poziție pentru a fi de nedăspărțiți. Pot aceștia să realizeze acest lucru după un număr finit de pași?

Cerință

Scrieți un program care determină, pentru mai multe scenarii, dacă Alex și Lorena pot ajunge pe aceiași poziție după un număr finit de pași. Pentru cerința $1$ se garantează că vom avea 2 oglinzi. Pentru cerința 2 vor fi cel puțin 2 oglinzi.

Date de intrare

Pe prima linie a fișierului oglinzifermecate.in se află $C$ reprezentând cerința care trebuie rezolvată
Pentru $(C=1)$ urmează un număr întreg $n$ reprezentând numărul de scenarii.

• Pentru fiecare dintre cele $n$ scenarii, se dau patru numere întregi: $a,$ $b,$ $x,$ $y,$
• $a$ și $b$ sunt pozițiile inițiale ale lui Alex și Lorena.
• $x$ și $y$ sunt pozițiile celor două oglinzi fixe.

Pentru $(C=2)$ urmează un număr întreg $n$ reprezentând numărul de scenarii.

• Pentru fiecare dintre cele $n$ scenarii, se dau trei numere întregi: $a,$ $b,$ $k,$
• Pe următoarea linie se află k numere naturale $x_1,$ $x_2,$ $...$ $x_k$
• $a$ și $b$ sunt pozițiile inițiale ale lui Alex și Lorena.
• $x_i$ este pozția oglindei cu indicele $i$.

Date de ieșire

Pe feicare linie a fișierului de ieșire oglinzifermecate.out se va găsi fie mesajul DA (dacă cei doi pot ajunge pe aceiași pozție), fie NU (dacă cei doi nu pot ajunge pe aceiași poziție).

Restricții și precizări

• Pentru teste în valoare de 10 puncte $C=1,$ $1 \leq n \leq 2*10^5,$ $0 \leq a,b,x,y \leq 10^9$, $x=y$
• Pentru teste în valoare de 10 puncte $C=1,$ $1 \leq n \leq 100,$ $0 \leq a,b,x,y \leq 100$
• Pentru teste în valoare de 10 puncte $C=1,$ $1 \leq n \leq 1000,$ $0 \leq a,b,x,y \leq 10^5$
• Pentru teste în valoare de 20 puncte $C=1,$ $1 \leq n \leq 2*10^5,$ $0 \leq a,b,x,y \leq 10^9$
  $S_k$ reprezintă suma k-urilor pe întreg testul
• Pentru teste în valoare de 10 puncte $C=2,$ $1 \leq n \leq 10^3,$ $2*n \leq S_k \leq 2*10^5,$ $0 \leq a,b,x_i \leq 10^9$, $x_1=$ $x_2=$ $...$ $=x_k$
• Pentru teste în valoare de 10 puncte $C=2,$ $1 \leq n \leq 2,$ $2*n \leq S_k \leq 100,$ $0 \leq a,b,x_i \leq 100$
• Pentru teste în valoare de 10 puncte $C=2,$ $1 \leq n \leq 10,$ $2*n \leq S_k \leq 10^3,$ $0 \leq a,b,x_i \leq 10^5$
• Pentru teste în valoare de 20 puncte $C=2,$ $1 \leq n \leq 10^3,$ $2*n \leq S_k \leq 2*10^5,$ $0 \leq a,b,x_i \leq 10^9$

Atenție! Două oglinzi se pot afla pe aceleași poziții!

Exemplul 1

oglinzifermecate.in

1 4
0 6 2 4
0 8 2 4
1 10 5 6
0 6 9 10

oglinzifermecate.out

NU
DA
NU
DA

Explicație

Pentru primul scenariu, la primul pas putem alege ca Alex (poziția $0$) să se oglindească cu oglinda de pe $2$, iar Lorena (poziția $6$) să se oglindească cu oglinda de poziția $4$. Cei doi ajung pe pozițiile $(4, 2)$. Se poate arăta că după oricâți pași cei doi nu se vor putea întâlni.
Pentru scenariul 2, cei doi se află la pozițiile $(0,8)$. După un pas ei pot ajunge pe pozițiile $(4,0)$. După al doilea pas ei pot ajunge pe pozițiile $(4,4)$.

Exemplul 2

oglinzifermecate.in

2
5
15 9 3
11 15 1
15 7 4
16 4 0 8
9 9 13
8 12 8 8 0 12 4 0 4 16 8 8 16
5 5 11
12 12 8 4 16 4 0 12 0 4 16
19 12 5
0 1 7 2 16

oglinzifermecate.out

NU
DA
DA
DA
NU

Explicație

Pentru scenariile 3 și 4 cei doi se află de la bun început pe aceleași pozitii, deci răspunsul este DA.