Deskripsi
Anda memiliki seekor Bangboo yang lucu, dan ia sedang berpartisipasi dalam "Petualangan Besar Marcel".
Bangboo ini bergerak di dalam ruang tiga dimensi. Titik awalnya adalah $(S_x, S_y, S_z)$, dan tujuannya adalah $(T_x, T_y, T_z)$. Anda dapat menganggapnya sebagai sebuah kubus satuan yang berpusat di $(S_x, S_y, S_z)$. Terdapat $n$ rintangan di dalam ruang tiga dimensi tersebut, yang masing-masing merupakan sebuah kubus satuan yang berpusat di $(x_i, y_i, z_i)$. Dijamin bahwa koordinat titik awal, tujuan, dan semua rintangan saling berbeda satu sama lain, serta pasti terdapat rintangan di $(S_x, S_y, S_z - 1)$ dan $(T_x, T_y, T_z - 1)$.
Bangboo dapat melakukan teleportasi. Pada setiap langkah, ia memiliki $m$ metode teleportasi yang tersedia. Misalkan saat ini ia berada di $(x, y, z)$. Metode teleportasi ke-$i$ akan mengirimnya ke $(x + a_i, y + b_i, z + c_i)$, yang kemudian diikuti dengan jatuh bebas. Secara formal, ia akan berteleportasi ke $(x + a_i, y + b_i, d)$, di mana $d$ adalah nilai maksimum yang memenuhi $d \le z + c_i$ dan terdapat rintangan di $(x + a_i, y + b_i, d - 1)$. Jika terdapat rintangan di $(x + a_i, y + b_i, z + c_i)$, atau jika tidak ada nilai $d$ yang memenuhi syarat, maka teleportasi ini tidak dapat dilakukan.
Tujuan Anda adalah membuat Bangboo mencapai tujuan dari titik awal dengan menggunakan jumlah langkah minimum. Jika tidak mungkin mencapai tujuan, keluarkan $-1$.
Masukan
Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 500$), yang menyatakan banyaknya kasus uji.
Untuk setiap kasus uji:
Baris pertama berisi dua bilangan bulat $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), yang masing-masing menyatakan banyaknya rintangan dan banyaknya metode teleportasi yang tersedia bagi Bangboo.
Baris kedua berisi enam bilangan bulat $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$), yang menyatakan titik awal dan tujuan Bangboo.
$n$ baris berikutnya masing-masing berisi tiga bilangan bulat $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), yang menyatakan koordinat rintangan ke-$i$. Dijamin bahwa pasti terdapat rintangan di $(S_x, S_y, S_z - 1)$ dan $(T_x, T_y, T_z - 1)$.
$m$ baris berikutnya masing-masing berisi tiga bilangan bulat $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), yang menyatakan metode teleportasi ke-$i$.
Untuk setiap kasus uji, dijamin bahwa semua koordinat masukan saling berbeda satu sama lain, dan semua metode teleportasi saling berbeda satu sama lain.
Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $10^3$, dan jumlah dari $m$ di seluruh kasus uji tidak melebihi $10^3$.
Keluaran
Untuk setiap kasus uji, keluarkan sebuah bilangan bulat pada satu baris, yang menyatakan jumlah langkah minimum yang diperlukan untuk mencapai tujuan dari titik awal. Jika tidak mungkin mencapai tujuan, keluarkan $-1$.
Contoh
Masukan 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
Keluaran 1
5 -1