Описание
У вас есть милый Банбу (Bangboo), и он участвует в «Большом приключении Марселя».
Этот Банбу перемещается в трёхмерном пространстве. Его начальная точка — $(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