Drone

설곽이는 미래형 공중 도시에서 드론을 이용해 이동한다. 도시에는 $N$개의 거점이 있으며, $i$번 거점의 좌표는 $(x_i,y_i,z_i)$이다.

드론은 한 번의 이동에서 현재 거점에서 다른 거점으로 이동할 수 있다. $u$번 거점에서 $v$번 거점으로 이동할 때 다음 값들이 사용된다.

• 이동 시간은 $|x_u-x_v|+|y_u-y_v|+|z_u-z_v|$이다.
• 소모 배터리는 $|x_u-x_v|+|y_u-y_v|+(z_u-z_v)^2$이다.

하나의 경로는 정수 $k \geq 0$과 거점 번호열 $p_0,p_1,\ldots,p_k$로 표현된다. 이때 $p_0$은 출발 거점, $p_k$는 도착 거점이며, 드론은 $p_{i-1}$번 거점에서 $p_i$번 거점으로 차례대로 이동한다 ($1 \leq i \leq k$). 같은 거점을 여러 번 방문해도 된다. $k=0$인 경우에는 이동하지 않는 경로이며, 이동 시간과 소모 배터리는 모두 $0$이다.

$q$번 이동 요청은 세 정수 $(a_q,b_q,t_q)$로 주어진다. 이는 $a_q$번 거점에서 $b_q$번 거점까지 총 이동 시간이 $t_q$ 이하인 경로 중에서, 소모 배터리의 최솟값을 구하라는 뜻이다.

각 이동 요청에 대해 조건을 만족하는 경로의 최소 소모 배터리를 구하여라. 조건을 만족하는 경로가 존재하지 않는 경우에는 $-1$을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $x_1\ y_1\ z_1$ $x_2\ y_2\ z_2$ $\vdots$ $x_N\ y_N\ z_N$ $a_1\ b_1\ t_1$ $a_2\ b_2\ t_2$ $\vdots$ $a_Q\ b_Q\ t_Q$

$Q$개의 줄에 걸쳐 답을 출력한다. $q$번째 줄에는 $q$번 이동 요청에 대한 최소 소모 배터리를 출력한다.

조건을 만족하는 경로가 존재하지 않는 경우에는 $-1$을 출력한다.

• $1 \leq N \leq 50$.
• $1 \leq Q \leq 200\ 000$.
• $-1\ 000\ 000 \leq x_i,y_i,z_i \leq 1\ 000\ 000$ ($1 \leq i \leq N$).
• $1 \leq a_q,b_q \leq N$ ($1 \leq q \leq Q$).
• $1 \leq t_q \leq 500$ ($1 \leq q \leq Q$).
• 서로 다른 두 거점이 같은 좌표를 가질 수 있다.