Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.