Codah ClubUshtrohu. Dërgo. Përmirësohu.
Hyr
Shqip
#00011B

z-mushrooms

Mr Little Z got really bored one day, and decided to watch a field where mushrooms are growing. He was so bored that he decided to give a name to each of mushroom that pops out of the ground.


The field can be imagined as a 2D plane, and each mushroom can pop out at some coordinate (x,y). As soon as the mushroom pops out of the ground Little Z gives it a name.


However, sometimes there are no mushrooms growing out for hours, and in that case little Z is playing the following game. He asks himself what is the name of the mushroom that is the closest to some coordinate (x,y) - by closest we mean the closest in Eculedian distance


You have to help Mr. Little Z by writhing a program that will keep track of all the mushrooms that are growing out of the ground, and answer questions about which mushroom is currently closest to some fixed point (x,y)


InputFrom the first line of standard input read an integer N, 1 <= N <= 100000. The following N lines will be in one of the two following formats:
- G [x] [y] [name], which is a character "G" followed by two real numbers (three decimal point precision) and a string (made of the letters of the English alphabet and digits 0-9, with max 20 characters). This line represents that there is a mushroom growing at (x,y), and little z named it with [name].
- Q [x] [y]. which is character "Q" followed by two real numbers (three decimal point precision). This line of input represents a question that you have to answer: what is the name of the mushroom closest to (x,y).

All the values of [x] and [y] will be in the range [0 10000]

OutputTo the standard output write the answers to all the "Q" questions from the input, each in a separate line. The output will have the same number of lines as the numbers of lines in the input that have "Q" question. If, for some questions there are two or more closest mushrooms with the same distance from (x,y), then output the one with the lexicographically smallest name.

Input:
4
G 1.000 1.000 boba
G 2.000 2.000 aleks
Q 1.500 1.500
Q 1.200 1.200
Output:
aleks
boba

Input:
4
G 1.000 1.000 boba
Q 100.000 100.000
G 2.000 1.000 dule
Q 100.000 100.000
Output:
boba
dule

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.