Descrizione
Hai un simpatico Bangboo che sta partecipando alla "Grande Avventura di Marcel".
Questo Bangboo si muove nello spazio tridimensionale. Il suo punto di partenza è $(S_x, S_y, S_z)$ e la sua destinazione è $(T_x, T_y, T_z)$. Puoi considerarlo come un cubo unitario centrato in $(S_x, S_y, S_z)$. Ci sono $n$ ostacoli nello spazio tridimensionale, ciascuno dei quali è un cubo unitario centrato in $(x_i, y_i, z_i)$. È garantito che le coordinate del punto di partenza, della destinazione e di tutti gli ostacoli sono a due a due distinte, e che devono esserci degli ostacoli in $(S_x, S_y, S_z - 1)$ e $(T_x, T_y, T_z - 1)$.
Il Bangboo può teletrasportarsi. Ad ogni passo, ha $m$ metodi di teletrasporto disponibili. Supponiamo che si trovi attualmente in $(x, y, z)$. L'$i$-esimo metodo di teletrasporto lo invia in $(x + a_i, y + b_i, z + c_i)$, dopodiché subisce una caduta libera. Formalmente, si teletrasporterà in $(x + a_i, y + b_i, d)$, dove $d$ è il valore massimo che soddisfa $d \le z + c_i$ e tale che ci sia un ostacolo in $(x + a_i, y + b_i, d - 1)$. Se c'è un ostacolo in $(x + a_i, y + b_i, z + c_i)$, oppure se non esiste un tale $d$, allora questo teletrasporto non può essere effettuato.
Il tuo obiettivo è far raggiungere la destinazione al Bangboo partendo dal punto di partenza usando il numero minimo di passi. Se è impossibile raggiungere la destinazione, stampa $-1$.
Input
La prima riga contiene un intero $T$ ($1 \le T \le 500$), che indica il numero di casi di test.
Per ciascun caso di test:
La prima riga contiene due interi $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), che indicano rispettivamente il numero di ostacoli e il numero di metodi di teletrasporto disponibili per il Bangboo.
La seconda riga contiene sei interi $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$), che indicano il punto di partenza e la destinazione del Bangboo.
Le successive $n$ righe contengono ciascuna tre interi $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), che indicano le coordinate dell'$i$-esimo ostacolo. È garantito che devono esserci degli ostacoli in $(S_x, S_y, S_z - 1)$ e $(T_x, T_y, T_z - 1)$.
Le successive $m$ righe contengono ciascuna tre interi $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), che indicano l'$i$-esimo metodo di teletrasporto.
Per ciascun caso di test, è garantito che tutte le coordinate in input sono a due a due distinte, e che tutti i metodi di teletrasporto sono a due a due distinti.
È garantito che la somma di $n$ su tutti i casi di test non supera $10^3$, e che la somma di $m$ su tutti i casi di test non supera $10^3$.
Output
Per ciascun caso di test, stampa un singolo intero su una riga, che indica il numero minimo di passi richiesti per raggiungere la destinazione dal punto di partenza. Se è impossibile raggiungere la destinazione, stampa $-1$.
Esempi
Input 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
Output 1
5 -1