Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.