Ruletta

.atsa amelborp al eletset caf as csaru.

Buzdi s-a relaxat gândindu-se la categoria sa preferată de probleme de informatică. Acum, acesta vrea să se distreze așa cum știe el cel mai bine, fiind un nerd în locuri de băieți mari, așa că Buzdi se duce la cel mai apropiat cazinou (de altfel și singurul...) să vadă noutățile. El găsește înăuntru o nouă ruletă, numită ruletta (nu știe nimeni de ce este scrisă cu doi de "t"...), și decide să se joace cu ea.

Ruletta este formată din două șiruri de $N$ numere naturale distincte, $A$ și $B$, și de două butoane aflate la ambele capete ale șirului $A$. Aceste butoane au următoarea semnificație:

1. Dacă butonul din stânga este apăsat, atunci șirul $A$ se permută circular la stânga. De exemplu, dacă $A = [1, 2, 3, 4]$, atunci, după apăsarea butonului stâng, $A = [2, 3, 4, 1]$.
2. Dacă butonul din dreapta este apăsat, atunci șirul $A$ se permută circular la dreapta. De exemplu, dacă $A = [1, 2, 3, 4]$, atunci, după apăsarea butonului drept, $A = [4, 1, 2, 3]$.

Ruletta nu este prea îndrăgită de jucători, pentru că nu are niciun scop, însă Buzdi este foarte atras de ea. După multe ore petrecute la rulettă, acesta are următoarea întrebare: este posibil să apăsăm pe cele două butoane de exact $K$ ori în total, astfel încât șirurile $A$ și $B$ să devină identice? Buzdi este prea distrat ca să mai gândească, așa că vă roagă pe voi să îl ajutați!

Cerință

Dându-se $T$ rulette, să se răspundă la întrebarea lui Buzdi pentru fiecare dintre acestea.

Date de intrare

Pe prima linie a fișierului de intrare ruletta.in se găsește un singur număr natural $T$. Pe următoarele linii se vor descrie cele $T$ rulette, după următoarea structură:

• Pe prima linie a descrierii se găsesc două numere naturale, $N$ și $K$, separate printr-un spațiu, cu semnificația din enunț.
• Pe următoarea linie a descrierii se găsesc $N$ numere naturale distincte, separate printr-un spațiu, reprezentând elementele șirului $A$.
• Pe următoarea linie a descrierii se găsesc $N$ numere naturale distincte, separate printr-un spațiu, reprezentând elementele șirului $B$.

Date de ieșire

Pe următoarele $T$ linii ale fișierului de ieșire ruletta.out se va găsi mesajul DA sau NU, reprezentând răspunsul la întrebarea lui Buzdi pentru ruletta respectivă.

Restricții și precizări

• Fie $S_N$ suma valorilor $N$ din cele $T$ rulette;
• $1 \leq N \leq 200 \ 000$;
• $1 \leq S_N \leq 10^6$;
• $0 \leq K \leq 2 \cdot 10^9$;
• $1 \leq A_i, B_i \leq 2 \cdot 10^9, 1 \leq i \leq N$;
• Două șiruri $A$ și $B$ de lungime $N$ sunt identice dacă $A_i = B_i, 1 \leq i \leq N$;

  #	Punctaj	Restricții
  0	0	Exemplul
  1	11	$K = 0$
  2	17	Dacă răspunsul pentru o rulettă este DA, atunci este suficient să apăsăm de $K$ ori doar pe un singur buton
  3	21	$0 \leq K \leq 2000$ și $1 \leq S_N \leq 10 \ 000$
  4	23	$1 \leq N \leq 2000$ și $1 \leq S_N \leq 10 \ 000$
  5	28	Fără restricții suplimentare

Exemplu

ruletta.in

2
6 3
1 2 3 4 5 6
4 5 6 1 2 3
5 4
2 10 3 12 5
12 5 100 10 3

ruletta.out

DA
NU

Explicație

Pentru prima rulettă, putem apăsa butonul stâng de $3$ ori, iar cele două șiruri vor deveni identice.
Pentru a doua rulettă, oricum am apăsa cele două butoane de $4$ ori în total, cele două șiruri nu vor deveni identice. Se pare că ruletta a venit și defectă...