Drone

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

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

• 이동 시간은 $|x_u-x_v|+|y_u-y_v|+|z_u-z_v|$이다.

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

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

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

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

$N\ Q$ $x_1\ y_1\ z_1$

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

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

• $1 \leq N \leq 50$.
• $1 \leq Q \leq 200\ 000$.
• $-1000000\le x_i,$ ().