Drone Docking Bay

A warehouse drone navigates by listening to nearby 3-D beacons. Each beacon has a position x, y, z and a docking bay type, like fast or heavy. When the drone approaches a location, it should dock at the type of the closest beacon.

You are asked to help the drone decide.

The first line of the input contains a single integer n representing the number of known beacons.

The next n lines each contain three floating-point numbers x y z followed by a single word for the docking bay type, describing one beacon’s position and type.

The next line contains a single integer q representing the number of approach positions to check.

The last q lines each contain three floating-point numbers x y z for the drone’s approach position.

For each approach position, print the docking bay type of the single nearest beacon. If several beacons have exactly the same distance from the approach position, print the type of the beacon that appears earliest in the input.

Input

Output

4
0 0 0 fast
2 0 0 heavy
0 2 0 standard
0 0 2 heavy
3
0.9 0.1 0.1
1.1 0 0
1 1 1

fast
heavy
fast

3
-1 0 0 light
3 0 0 heavy
0 0 4 fast
2
2 1 0
2 5 0

heavy
heavy

2
0 0 0 alpha
0 0 2 beta
3
0 0 1
0 0 1.001
1 1 1

alpha
beta
alpha

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue