你有一只可爱的邦布（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