Mô tả bài toán
Bạn có một chú Bangboo đáng yêu, và chú đang tham gia vào "Cuộc đại phiêu lưu của Marcel".
Chú Bangboo này di chuyển trong không gian ba chiều. Điểm xuất phát của nó là $(S_x, S_y, S_z)$, và đích đến là $(T_x, T_y, T_z)$. Bạn có thể coi nó như một khối lập phương đơn vị có tâm tại $(S_x, S_y, S_z)$. Có $n$ chướng ngại vật trong không gian ba chiều, mỗi chướng ngại vật là một khối lập phương đơn vị có tâm tại $(x_i, y_i, z_i)$. Đảm bảo rằng tọa độ của điểm xuất phát, đích đến và tất cả các chướng ngại vật đôi một khác nhau, đồng thời tại $(S_x, S_y, S_z - 1)$ và $(T_x, T_y, T_z - 1)$ chắc chắn có chướng ngại vật.
Bangboo có thể dịch chuyển tức thời. Ở mỗi bước, nó có $m$ phương thức dịch chuyển khả dụng. Giả sử hiện tại nó đang ở $(x, y, z)$. Phương thức dịch chuyển thứ $i$ sẽ đưa nó tới $(x + a_i, y + b_i, z + c_i)$, sau đó nó sẽ rơi tự do. Một cách hình thức, nó sẽ dịch chuyển tới $(x + a_i, y + b_i, d)$, trong đó $d$ là giá trị lớn nhất thỏa mãn $d \le z + c_i$ và tại $(x + a_i, y + b_i, d - 1)$ có một chướng ngại vật. Nếu tại $(x + a_i, y + b_i, z + c_i)$ có chướng ngại vật, hoặc không tồn tại giá trị $d$ nào thỏa mãn, thì không thể thực hiện lần dịch chuyển này.
Mục tiêu của bạn là giúp Bangboo đi từ điểm xuất phát tới đích đến với số bước ít nhất. Nếu không thể tới được đích đến, hãy in ra $-1$.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 500$), biểu thị số lượng bộ dữ liệu.
Đối với mỗi bộ dữ liệu:
Dòng đầu tiên chứa hai số nguyên $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), lần lượt biểu thị số lượng chướng ngại vật và số lượng phương thức dịch chuyển mà Bangboo có thể dùng.
Dòng thứ hai chứa sáu số nguyên $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$), biểu thị điểm xuất phát và đích đến của Bangboo.
$n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), biểu thị tọa độ của chướng ngại vật thứ $i$. Đảm bảo rằng tại $(S_x, S_y, S_z - 1)$ và $(T_x, T_y, T_z - 1)$ chắc chắn có chướng ngại vật.
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), biểu thị phương thức dịch chuyển thứ $i$.
Đối với mỗi bộ dữ liệu, đảm bảo rằng tất cả các tọa độ trong dữ liệu vào đôi một khác nhau, và tất cả các phương thức dịch chuyển đôi một khác nhau.
Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^3$, và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $10^3$.
Kết quả
Đối với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng, biểu thị số bước ít nhất cần thiết để đi từ điểm xuất phát tới đích đến. Nếu không thể tới được đích đến, hãy in ra $-1$.
Ví dụ
Dữ liệu vào 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
Kết quả 1
5 -1