Beskrivelse
Du har en søt Bangboo, og den deltar i «Marcels store eventyr».
Denne Bangbooen beveger seg i et tredimensjonalt rom. Startpunktet dens er $(S_x, S_y, S_z)$, og målet er $(T_x, T_y, T_z)$. Du kan betrakte den som en enhetskube med sentrum i $(S_x, S_y, S_z)$. Det er $n$ hindringer i det tredimensjonale rommet, som hver er en enhetskube med sentrum i $(x_i, y_i, z_i)$. Det garanteres at koordinatene til startpunktet, målet og alle hindringene er parvis ulike, og at det må være hindringer i $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.
Bangbooen kan teleportere. I hvert steg har den $m$ tilgjengelige teleporteringsmetoder. Anta at den for øyeblikket befinner seg i $(x, y, z)$. Den $i$-te teleporteringsmetoden sender den til $(x + a_i, y + b_i, z + c_i)$, hvoretter den faller fritt. Formelt vil den teleportere til $(x + a_i, y + b_i, d)$, der $d$ er den maksimale verdien som oppfyller $d \le z + c_i$ og at det er en hindring i $(x + a_i, y + b_i, d - 1)$. Hvis det er en hindring i $(x + a_i, y + b_i, z + c_i)$, eller hvis ingen slik $d$ finnes, kan ikke denne teleporteringen utføres.
Målet ditt er å få Bangbooen til å nå målet fra startpunktet med færrest mulig steg. Hvis det er umulig å nå målet, skriv ut $-1$.
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 500$), som angir antallet testtilfeller.
For hvert testtilfelle:
Den første linjen inneholder to heltall $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), som angir henholdsvis antallet hindringer og antallet teleporteringsmetoder som er tilgjengelige for Bangbooen.
Den andre linjen inneholder seks heltall $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$), som angir startpunktet og målet til Bangbooen.
De neste $n$ linjene inneholder hver tre heltall $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), som angir koordinatene til den $i$-te hindringen. Det garanteres at det må være hindringer i $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.
De neste $m$ linjene inneholder hver tre heltall $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), som angir den $i$-te teleporteringsmetoden.
For hvert testtilfelle garanteres det at alle inndatakoordinater er parvis ulike, og at alle teleporteringsmetoder er parvis ulike.
Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^3$, og at summen av $m$ over alle testtilfeller ikke overstiger $10^3$.
Utdata
For hvert testtilfelle skal du skrive ut ett enkelt heltall på én linje, som angir det minste antallet steg som kreves for å nå målet fra startpunktet. Hvis det er umulig å nå målet, skriv ut $-1$.
Eksempler
Inndata 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
Utdata 1
5 -1