問題文
あなたはかわいいボンプ(Bangboo)を連れており、そのボンプは「マルセルの大冒険」に参加しています。
このボンプは 3 次元空間内を移動します。開始位置は $(S_x, S_y, S_z)$、目的位置は $(T_x, T_y, T_z)$ です。ボンプは $(S_x, S_y, S_z)$ を中心とする単位立方体とみなすことができます。3 次元空間には $n$ 個の障害物があり、各障害物は $(x_i, y_i, z_i)$ を中心とする単位立方体です。開始位置、目的位置、およびすべての障害物の座標は互いに異なることが保証されており、また $(S_x, S_y, S_z - 1)$ と $(T_x, T_y, T_z - 1)$ には必ず障害物が存在します。
ボンプはテレポートすることができます。各ステップにおいて、$m$ 種類のテレポート方法が利用可能です。現在 $(x, y, z)$ にいるとします。$i$ 番目のテレポート方法を使うと $(x + a_i, y + b_i, z + c_i)$ に送られ、その後自由落下します。形式的には、$(x + a_i, y + b_i, d)$ にテレポートします。ここで $d$ は、$d \le z + c_i$ かつ $(x + a_i, y + b_i, d - 1)$ に障害物が存在するような最大の値です。もし $(x + a_i, y + b_i, z + c_i)$ に障害物が存在する場合、または条件を満たす $d$ が存在しない場合は、このテレポートを行うことはできません。
あなたの目標は、ボンプを開始位置から目的位置まで最小のステップ数で到達させることです。目的位置に到達できない場合は $-1$ を出力してください。
入力
1 行目にはテストケースの数を表す整数 $T$ ($1 \le T \le 500$) が与えられます。
各テストケースについて:
1 行目には、障害物の数とボンプが利用できるテレポート方法の数を表す 2 つの整数 $n, m$ ($2 \le n \le 10^3$、$1 \le m \le 10^3$) が与えられます。
2 行目には、ボンプの開始位置と目的位置を表す 6 つの整数 $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$) が与えられます。
続く $n$ 行には、それぞれ $i$ 番目の障害物の座標を表す 3 つの整数 $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$) が与えられます。$(S_x, S_y, S_z - 1)$ と $(T_x, T_y, T_z - 1)$ には必ず障害物が存在することが保証されます。
続く $m$ 行には、それぞれ $i$ 番目のテレポート方法を表す 3 つの整数 $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$) が与えられます。
各テストケースについて、入力されるすべての座標は互いに異なり、すべてのテレポート方法も互いに異なることが保証されます。
すべてのテストケースにおける $n$ の総和は $10^3$ を超えず、$m$ の総和も $10^3$ を超えないことが保証されます。
出力
各テストケースについて、開始位置から目的位置に到達するために必要な最小のステップ数を表す整数を 1 行に出力してください。到達できない場合は $-1$ を出力してください。
入出力例
入力例 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
出力例 1
5 -1