Опис
У вас є милий Банбу (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