Description
You have a cute Bangboo, and it is participating in "Marcel's Great Adventure".
This Bangboo moves in three-dimensional space. Its starting point is $(S_x, S_y, S_z)$, and its destination is $(T_x, T_y, T_z)$. You may regard it as a unit cube centered at $(S_x, S_y, S_z)$. There are $n$ obstacles in the three-dimensional space, each of which is a unit cube centered at $(x_i, y_i, z_i)$. It is guaranteed that the coordinates of the starting point, the destination, and all obstacles are pairwise distinct, and that there must be obstacles at $(S_x, S_y, S_z - 1)$ and $(T_x, T_y, T_z - 1)$.
The Bangboo can teleport. At each step, it has $m$ available teleportation methods. Suppose it is currently at $(x, y, z)$. The $i$-th teleportation method sends it to $(x + a_i, y + b_i, z + c_i)$, after which it undergoes free fall. Formally, it will teleport to $(x + a_i, y + b_i, d)$, where $d$ is the maximum value satisfying $d \le z + c_i$ and there is an obstacle at $(x + a_i, y + b_i, d - 1)$. If there is an obstacle at $(x + a_i, y + b_i, z + c_i)$, or if no such $d$ exists, then this teleportation cannot be performed.
Your goal is to make the Bangboo reach the destination from the starting point using the minimum number of steps. If it is impossible to reach the destination, output $-1$.
Input
The first line contains an integer $T$ ($1 \le T \le 500$), denoting the number of test cases.
For each test case:
The first line contains two integers $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), denoting the number of obstacles and the number of teleportation methods available to the Bangboo, respectively.
The second line contains six integers $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$), denoting the starting point and the destination of the Bangboo.
The next $n$ lines each contain three integers $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), denoting the coordinates of the $i$-th obstacle. It is guaranteed that there must be obstacles at $(S_x, S_y, S_z - 1)$ and $(T_x, T_y, T_z - 1)$.
The next $m$ lines each contain three integers $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), denoting the $i$-th teleportation method.
For each test case, it is guaranteed that all input coordinates are pairwise distinct, and all teleportation methods are pairwise distinct.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^3$, and the sum of $m$ over all test cases does not exceed $10^3$.
Output
For each test case, output a single integer in one line, denoting the minimum number of steps required to reach the destination from the starting point. If it is impossible to reach the destination, output $-1$.
Examples
Input 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
Output 1
5 -1