비밀 요원

2000년 전, 지금 이 자리에는 도시국가 인호국의 성이 서 있었다. 인호국의 성은 $1$번부터 $N$번까지 번호가 붙은 망루 $N$개와, 두 망루를 잇는 성벽 $M$개로 이루어져 있다. 성벽은 선분 모양이고, 어떤 두 성벽도 망루가 아닌 지점에서는 만나지 않으며, 어느 망루에서든 성벽을 타고 다른 모든 망루로 갈 수 있다. 인호국의 왕 인호는 이 성 안에 국가 기밀을 숨겨 두었다.

경쟁 관계인 도시국가 민석국의 왕 민석이는 그 기밀을 캐내려고 비밀 요원을 성으로 들여보낸다. 요원은 매우 빨라서 성벽이 가로막지 않는 한 이동 시간을 무시할 수 있다. 성벽을 넘을 때는 그 성벽의 높이만큼 시간이 걸린다. 망루는 통과하지 못하므로, 요원은 언제나 망루가 아닌 지점에서 성벽을 넘는다.

민석이는 요원에게 지점 $Q$개를 순서대로 방문하라고 명령했다. 각 지점은 성벽이나 망루와 겹치지 않는다. 요원은 성에서 무한히 멀리 떨어진 곳에서 출발해 $1$번 지점, $2$번 지점의 순서로 찾아간다. 각 구간마다 요원이 쓰는 최소 시간을 구하자.

첫째 줄에 망루의 개수 $N$ ($1 \le N \le 200\,000$)과 성벽의 개수 $M$ ($N-1 \le M \le N+100$)이 주어진다.

다음 $N$개 줄에는 $i$번 망루의 좌표 $x_i$와 $y_i$가 순서대로 주어진다. ($|x_i|, |y_i| \le 10^9$)

다음 $M$개 줄에는 성벽이 잇는 두 망루의 번호 $u_i$와 $v_i$, 그리고 그 성벽의 높이 $h_i$가 주어진다. ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le h_i \le 10^9$)

같은 두 망루를 잇는 성벽은 많아야 하나이고, 어떤 두 성벽도 망루가 아닌 지점에서는 만나지 않는다. 임의의 두 망루 사이는 성벽을 타고 오갈 수 있다.

다음 줄에 명령의 개수 $Q$ ($1 \le Q \le 200\,000$)가 주어진다.

다음 $Q$개 줄에는 방문할 지점의 좌표 $a_i$와 $b_i$가 순서대로 주어진다. ($|a_i|, |b_i| \le 10^9$)

모든 지점은 성벽이나 망루와 겹치지 않는다.

$Q$개 줄을 출력한다. $i$번째 줄에는 $i-1$번 지점에서 $i$번 지점으로 가는 최소 시간을 출력한다. $0$번 지점의 좌표는 $(\infty, \infty)$, 즉 성에서 무한히 먼 곳으로 본다.

아래 그림은 망루 4개와 성벽 5개로 이루어진 성, 그리고 순서대로 방문하는 지점 3개를 나타낸다.