문제 설명
당신에게는 귀여운 방부(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$을 출력하세요.
입력
첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $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$개의 줄에는 각각 $i$번째 장애물의 좌표를 나타내는 세 정수 $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$번째 순간이동 방법을 나타내는 세 정수 $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$)가 주어집니다.
각 테스트 케이스에 대해 입력으로 주어지는 모든 좌표는 서로 다르며, 모든 순간이동 방법도 서로 다름이 보장됩니다.
모든 테스트 케이스에서 $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