새총

농부 존이 농장 일 가운데 가장 싫어하는 것은 거름을 잔뜩 실어 나르는 일이다. 이 일을 줄이려고 존은 별난 방법을 떠올렸다. 트랙터에 수레를 달아 두 지점 사이로 거름을 옮기는 대신, 거대한 거름 새총으로 공중에 쏘아 보내는 것이다. (무엇이 잘못될 수 있겠는가)

존의 농장은 곧게 뻗은 길 하나를 따라 놓여 있다. 그래서 농장의 모든 위치를 그 길 위의 좌표 하나로, 즉 수직선 위의 점으로 나타낸다. 존은 새총 $N$개를 세웠다 ($1 \leq N \leq 10^5$). $i$번 새총은 세 정수 $x_i$, $y_i$, $t_i$로 주어지며, 위치 $x_i$에 있는 거름을 단 $t_i$의 시간에 위치 $y_i$로 쏘아 보낸다.

옮겨야 할 거름 더미는 $M$개다 ($1 \leq M \leq 10^5$). $j$번 더미는 위치 $a_j$에서 위치 $b_j$로 옮겨야 한다. 트랙터로 거름을 거리 $d$만큼 나르면 $d$의 시간이 걸린다. 존은 더미 하나마다 새총을 최대 한 번까지 쓸 수 있게 해서 이 시간을 줄이려고 한다. 거름을 싣지 않은 채 트랙터만 움직이는 시간은 세지 않는다.

거름 더미 $M$개 각각에 대해, 새총을 최대 한 번 쓸 수 있을 때의 최소 운반 시간을 구하라.

첫째 줄에 $N$과 $M$이 주어진다. 다음 $N$개의 줄에는 새총 하나를 나타내는 세 정수 $x_i$, $y_i$, $t_i$가 주어진다 ($0 \leq x_i, y_i, t_i \leq 10^9$). 마지막 $M$개의 줄에는 옮겨야 할 거름 더미를 나타내는 두 정수 $a_j$와 $b_j$가 주어진다.

거름 더미마다 한 줄씩, 모두 $M$개의 줄에 최소 운반 시간을 출력한다.

예제에서 첫 번째 거름 더미는 위치 1에서 위치 12로 옮겨야 한다. 새총을 쓰지 않으면 11의 시간이 걸린다. 첫 번째 새총을 쓰면 새총의 출발 지점인 위치 0까지 옮기는 데 1, 거름을 공중으로 날려 새총의 도착 지점인 위치 10에 떨어뜨리는 데 1, 거기서 위치 12까지 옮기는 데 2가 들어 모두 4다. 두 번째 더미는 새총을 쓰지 않는 편이 가장 빠르고, 세 번째 더미는 두 번째 새총을 쓰는 편이 가장 빠르다.