텔레포트

2차원 평면 위에 $N$개의 도시가 있다. 일부 도시는 특별한 도시이다. $(r_1, c_1)$에 있는 도시에서 $(r_2, c_2)$에 있는 도시로 가는 이동 시간은 $|r_1 - r_2| + |c_1 - c_2|$와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 $T$이다.

두 도시의 쌍 $M$개가 주어졌을 때, 최소 이동 시간을 구해보자.

첫째 줄에 도시의 수 $N$, 텔레포트하는데 걸리는 시간 $T$가 주어진다.

둘째 줄부터 $N$개의 줄에 도시의 정보를 의미하는 세 정수 $s, x, y$가 1번 도시부터 $N$번 도시까지 순서대로 주어진다. $s$가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. $(x, y)$는 도시의 좌표이다.

다음 줄에는 $M$이 주어지고, 다음 $M$개의 줄에는 두 도시 $A$와 $B$가 주어진다.

총 $M$개의 줄에 걸쳐서 $A$에서 $B$에 가는 최소 이동 시간을 출력한다.

• $2 \le N \le 1,000$
• $1 \le T \le 2,000$
• $1 \le M \le 1,000$
• $0 \le x, y \le 1,000$
• $A \neq B$
• 두 도시의 좌표가 같은 경우는 없다.