Teleport

There are $N$ cities on a two-dimensional plane. Some of the cities are special. The travel time from the city at $(r_1, c_1)$ to the city at $(r_2, c_2)$ is $|r_1 - r_2| + |c_1 - c_2|$. If both cities are special, you may also travel between them by teleport. A teleport takes $T$ time.

Given $M$ pairs of cities, find the minimum travel time for each pair.

The first line gives the number of cities $N$ and the time a teleport takes $T$.

The next $N$ lines give three integers $s, x, y$ describing the cities, in order from city 1 to city $N$. If $s$ is 1, the city is special; if $s$ is 0, it is not special. $(x, y)$ is the coordinate of the city.

The next line gives $M$, and the following $M$ lines each give two cities $A$ and $B$.

Print the minimum travel time from $A$ to $B$, one value per line, over $M$ lines.

• $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$
• No two cities share the same coordinate.