AlgoLiga 2018

Jest rok 2214. Czwarty wymiar od jakiegoś czasu został bardzo dobrze okiełznany. Od kilku lat poruszanie się w czasie nie stanowi problemu. Niestety, każdy kto cofnął się w czasie nigdy nie powrócił do teraźniejszości, a nawet nie został w żaden sposób naznaczony historią. Dziś kilku ochotników (w tym Jasio) zostali przetransportowani do "czterowymiarowego" sześcianu. Oczywiście sześcian jest trójwymiarowy, ale poruszanie się po nim jest bardzo trudne ze względu na ingerencję czwartego wymiaru - czasu. Aby wygrać główną nagrodę (przetrwać), uczestnicy eksperymentu muszą dostać się z jednego jednostkowego podsześcianu do drugiego. Na początku bohaterowie zdarzenia myśleli, że aby przedostać się z jednej komnaty (jednostkowego sześcianu) do drugiej wystarczy po prostu do niej przejść. Niestety przejście było pozorne. Jasio zauważył, że komnaty mają przypisane numery. Każda komnata to sześcian, w którym są drzwi do wszystkich sąsiadujących sześcianów. Uczestnicy mogą poruszać się w następujący sposób:

• wyznaczają największy wspólny dzielnik numeru komnaty, w której się znajdują i numeru sąsiedniej. Następnie przemieszczają się do komnaty oddalonej o NWD tych liczb w danym kierunku.
• jeśli liczby sąsiednich komnat są względnie pierwsze, uczestnicy nie mogą przejść do następnej komnaty w danym kierunku
• jeśli NWD jest większe niż liczba komnat w danym kierunku sześcianu, numer komnaty jest wyznaczany z drugiej strony sześcianu (należy wykonać odpowiednią modulację)

Należy określić, czy uczestnicy mają szansę przejść z początkowej komnaty do komnaty, w której jest wyjście z całego sześcianu.

Wejście

W pierwszym wierszu jedna niewielka liczba określająca liczbę zestawów danych. 

Specyfikacja każdego zestawu:

W pierwszym wierszu dwie liczby n i q gdzie 0 < n < 51 oraz q < 1001, oznaczające odpowiednio długość boku sześcianu oraz liczbę zapytań. 

Następnie n macierzy n x n definiujące kolejne kondygnacje sześcianu. Każda wartość kondygnacji należy do przedziału [1..10⁶].

Następnie q zapytań składających się z sześciu liczb: x_p, y_p, z_p, x_k, y_k, z_k określające odpowiednio współrzędne początkowe jednostkowego sześcianu, w którym znajdują się uczestnicy gry oraz współrzędne sześcianu do którego uczestnicy muszą dotrzeć. (x - numer kondygnacji, y - numer wiersza danej kondygnacji, z - numer kolumny danego wiersza). W testach nie ma pustych wierszy jak w przykładzie.

Uwaga! Przy rozwiązywaniu tego zadania należy zwrócić uwagę na ograniczenia stosu.

Wyjście

Dla każdego zapytania napis Tak, jeśli istnieje droga z początkowego sześcianu do końcowego lub napis Nie w przeciwnym razie.

Przykład

Wejście:
1
3 4
1 2 3
4 5 6
7 8 9

2 3 4
5 6 7
8 2 10

11 12 13
14 14 16
20 18 20

0 0 0 2 2 2
1 1 1 2 2 1
2 0 1 2 2 1
0 2 1 0 1 2

Wyjście:
Nie
Nie
Tak
Nie