# CSAcademy 23 B. Fast Travel ( Greedy )

Round #23 (Div. 2 only)

2≤N≤1000
1≤T≤2000
0≤Q≤1000
0≤x,y≤1000
There are no two points that share the same coordinates.

O( Q * N ) / O( N )

```N, T = map( int, input().split() )
S = []
X = []
Y = []
for i in range( N ):
s, x, y = map( int, input().split() )
S.append( s )
X.append( x )
Y.append( y )
Q = int( input() )
for qi in range( Q ):
A, B = map( int, input().split() )
A -= 1
B -= 1
ans = abs( X[ A ] - X[ B ] ) + abs( Y[ A ] - Y[ B ] )
if S[ A ] and S[ B ]:
ans = min( ans, T )
mina, minb = int( 1e9 ), int( 1e9 )
for i in range( N ):
if not S[ i ]: continue
if i != A and mina > abs( X[ A ] - X[ i ] ) + abs( Y[ A ] - Y[ i ] ):
mina = abs( X[ A ] - X[ i ] ) + abs( Y[ A ] - Y[ i ] )
if i != B and minb > abs( X[ B ] - X[ i ] ) + abs( Y[ B ] - Y[ i ] ):
minb = abs( X[ B ] - X[ i ] ) + abs( Y[ B ] - Y[ i ] )
if S[ A ] and not S[ B ]:
ans = min( ans, T + minb )
if not S[ A ] and S[ B ]:
ans = min( ans, T + mina )
if not S[ A ] and not S[ B ]:
ans = min( ans, T + mina + minb )
print( ans )
```