16958번 - 텔레포트

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

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

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

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

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

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

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