題目描述
你有一隻得意嘅邦布(Bangboo),佢正喺度參加「Marcel 嘅大冒險」。
呢隻邦布喺三維空間入面移動。佢嘅起點係 $(S_x, S_y, S_z)$,終點係 $(T_x, T_y, T_z)$。你可以將佢當做一個以 $(S_x, S_y, S_z)$ 為中心嘅單位立方體。三維空間入面存在 $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$。
輸入格式
第一行包含一個整數 $T$($1 \le T \le 500$),代表測試數據嘅數量。
對於每組測試數據:
第一行包含兩個整數 $n, m$($2 \le n \le 10^3$,$1 \le m \le 10^3$),分別代表障礙物嘅數量同埋邦布可用嘅傳送方式數量。
第二行包含六個整數 $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$ 行,每行包含三個整數 $x_i, y_i, z_i$($0 \le x_i, y_i, z_i \le 10^9$),代表第 $i$ 個障礙物嘅座標。保證喺 $(S_x, S_y, S_z - 1)$ 同 $(T_x, T_y, T_z - 1)$ 處一定有障礙物。
接住落嚟嘅 $m$ 行,每行包含三個整數 $a_i, b_i, c_i$($|a_i|, |b_i|, |c_i| \le 10^9$),代表第 $i$ 種傳送方式。
對於每組測試數據,保證所有輸入嘅座標兩兩唔同,而且所有傳送方式兩兩唔同。
保證所有測試數據嘅 $n$ 之和唔超過 $10^3$,而且 $m$ 之和唔超過 $10^3$。
輸出格式
對於每組測試數據,喺一行入面輸出一個整數,代表由起點到達終點所需嘅最少步數。如果無辦法到達終點,就輸出 $-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