K-sweep: How Many Neighbors Should I Ask?

A newcomer arrives in a busy town. They know where some friendly locals stand and what direction each one would give: left or right. At different street corners, the newcomer asks more and more nearby locals and writes down how the advice changes. Distances are straight-line distances from the initial corner.

For each corner, you are asked to predict the direction after asking the 1 nearest local, then the 2 nearest, then 3, and so on up to all n nearest locals. If two locals have exactly the same distance from the corner, you should consider the one that appeared earlier in the input.

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

The next n lines each contain two floating-point numbers x y followed by a direction (left or right), describing one local’s position and advice.

The next line contains a single integer q representing the number of street corners to check.
The last q lines each contain two floating-point numbers x y for a corner’s position.

For each corner, print n space-separated tokens on one line - the predictions for k = 1, 2, …, n using the fixed neighbor ordering for that corner.