Opposite Day Bread

A rebellious bakery wants to be different from its neighbors. Each neighbor bakery is labeled with what it usually bakes at its spot - one of two flavors: sweet or salty. For any new location the bakery considers, it first looks at k neighbors’ flavors based on their locations with straight-line (Euclidean L2) distance, then it picks the opposite flavor.

The first line of the input contains a single integer n representing the number of known bakeries. The next n lines each contain two floating-point numbers x y followed by a flavor for that spot: either sweet or salty.

The next line contains a single integer k.

The following line contains a single integer q representing the number of candidate locations. The last q lines each contain two floating-point numbers x y for a location to check.

For each location, print the flavor the bakery will pick for that spot. If there are multiple neighbors with the same distance, you should pick the ones that appear first in the input.