Kuvaus
Sinulla on söpö Bangboo, joka osallistuu ”Marcelin suureen seikkailuun”.
Tämä Bangboo liikkuu kolmiulotteisessa avaruudessa. Sen lähtöpiste on $(S_x, S_y, S_z)$ ja määränpää $(T_x, T_y, T_z)$. Voit ajatella sitä yksikkökuutiona, jonka keskipiste on $(S_x, S_y, S_z)$. Kolmiulotteisessa avaruudessa on $n$ estettä, joista jokainen on yksikkökuutio keskipisteenään $(x_i, y_i, z_i)$. On taattu, että lähtöpisteen, määränpään ja kaikkien esteiden koordinaatit ovat pareittain eri suuria ja että pisteissä $(S_x, S_y, S_z - 1)$ ja $(T_x, T_y, T_z - 1)$ on oltava esteet.
Bangboo voi teleportata. Jokaisella askeleella sillä on käytettävissään $m$ teleporttaustapaa. Oletetaan, että se on tällä hetkellä pisteessä $(x, y, z)$. $i$-s teleporttaustapa lähettää sen pisteeseen $(x + a_i, y + b_i, z + c_i)$, minkä jälkeen se putoaa vapaasti. Muodollisesti se teleporttaa pisteeseen $(x + a_i, y + b_i, d)$, missä $d$ on suurin arvo, jolla $d \le z + c_i$ ja pisteessä $(x + a_i, y + b_i, d - 1)$ on este. Jos pisteessä $(x + a_i, y + b_i, z + c_i)$ on este tai tällaista arvoa $d$ ei ole olemassa, tätä teleporttausta ei voida suorittaa.
Tavoitteenasi on saada Bangboo pääsemään lähtöpisteestä määränpäähän mahdollisimman vähillä askeleilla. Jos määränpäähän on mahdotonta päästä, tulosta $-1$.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 500$), joka ilmaisee testitapausten lukumäärän.
Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää kaksi kokonaislukua $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), jotka ilmaisevat esteiden lukumäärän ja Bangboon käytettävissä olevien teleporttaustapojen lukumäärän.
Toinen rivi sisältää kuusi kokonaislukua $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$), jotka ilmaisevat Bangboon lähtöpisteen ja määränpään.
Seuraavat $n$ riviä sisältävät kukin kolme kokonaislukua $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), jotka ilmaisevat $i$-nnen esteen koordinaatit. On taattu, että pisteissä $(S_x, S_y, S_z - 1)$ ja $(T_x, T_y, T_z - 1)$ on oltava esteet.
Seuraavat $m$ riviä sisältävät kukin kolme kokonaislukua $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), jotka ilmaisevat $i$-nnen teleporttaustavan.
Jokaisessa testitapauksessa on taattu, että kaikki syötteen koordinaatit ovat pareittain eri suuria ja kaikki teleporttaustavat ovat pareittain erilaisia.
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^3$ eikä lukujen $m$ summa yli kaikkien testitapausten ylitä arvoa $10^3$.
Tuloste
Tulosta jokaiselle testitapaukselle omalle rivilleen yksi kokonaisluku, joka ilmaisee pienimmän askelmäärän lähtöpisteestä määränpäähän pääsemiseksi. Jos määränpäähän on mahdotonta päästä, tulosta $-1$.
Esimerkit
Syöte 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
Tuloste 1
5 -1