Opis
Masz uroczego Bangboo, który bierze udział w „Wielkiej Przygodzie Marcela”.
Ten Bangboo porusza się w przestrzeni trójwymiarowej. Jego punktem startowym jest $(S_x, S_y, S_z)$, a punktem docelowym $(T_x, T_y, T_z)$. Możesz traktować go jako sześcian jednostkowy o środku w $(S_x, S_y, S_z)$. W przestrzeni trójwymiarowej znajduje się $n$ przeszkód, z których każda jest sześcianem jednostkowym o środku w $(x_i, y_i, z_i)$. Gwarantuje się, że współrzędne punktu startowego, punktu docelowego oraz wszystkich przeszkód są parami różne, a także że w $(S_x, S_y, S_z - 1)$ oraz $(T_x, T_y, T_z - 1)$ muszą znajdować się przeszkody.
Bangboo potrafi się teleportować. W każdym kroku ma do wyboru $m$ sposobów teleportacji. Załóżmy, że aktualnie znajduje się w $(x, y, z)$. $i$-ty sposób teleportacji przenosi go do $(x + a_i, y + b_i, z + c_i)$, po czym następuje swobodne spadanie. Formalnie, przeteleportuje się on do $(x + a_i, y + b_i, d)$, gdzie $d$ jest największą wartością spełniającą $d \le z + c_i$, dla której w $(x + a_i, y + b_i, d - 1)$ znajduje się przeszkoda. Jeśli w $(x + a_i, y + b_i, z + c_i)$ znajduje się przeszkoda lub takie $d$ nie istnieje, to tej teleportacji nie można wykonać.
Twoim celem jest sprawienie, aby Bangboo dotarł z punktu startowego do punktu docelowego w minimalnej liczbie kroków. Jeśli dotarcie do punktu docelowego jest niemożliwe, wypisz $-1$.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 500$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego:
Pierwszy wiersz zawiera dwie liczby całkowite $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), oznaczające odpowiednio liczbę przeszkód oraz liczbę sposobów teleportacji dostępnych dla Bangboo.
Drugi wiersz zawiera sześć liczb całkowitych $S_x, S_y, S_z, T_x, T_y, T_z$ ($0 \le S_x, S_y, S_z, T_x, T_y, T_z \le 10^9$), oznaczających punkt startowy i punkt docelowy Bangboo.
Kolejne $n$ wierszy zawiera po trzy liczby całkowite $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), oznaczające współrzędne $i$-tej przeszkody. Gwarantuje się, że w $(S_x, S_y, S_z - 1)$ oraz $(T_x, T_y, T_z - 1)$ muszą znajdować się przeszkody.
Kolejne $m$ wierszy zawiera po trzy liczby całkowite $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), oznaczające $i$-ty sposób teleportacji.
Dla każdego przypadku testowego gwarantuje się, że wszystkie podane na wejściu współrzędne są parami różne oraz wszystkie sposoby teleportacji są parami różne.
Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^3$, a suma $m$ po wszystkich przypadkach testowych nie przekracza $10^3$.
Wyjście
Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą oznaczającą minimalną liczbę kroków potrzebnych na dotarcie z punktu startowego do punktu docelowego. Jeśli dotarcie do punktu docelowego jest niemożliwe, wypisz $-1$.
Przykłady
Wejście 1
2 6 4 3 3 3 5 5 5 3 3 2 5 5 4 5 5 7 4 5 5 2 3 2 4 1 1 -1 0 3 2 -2 -1 1 4 9 1 0 0 3 2 0 0 1 1 1 1 0 0 0 1 1 0 1 1 2 1 1 1 1 1 2
Wyjście 1
5 -1