It was just a fortnight ago when something strange happened. The well-known bacteriologist Kleofásh was conducting an experiment with `red-and-green' bacteria. Suddenly, his mind went blank... In the morning, he found himself lying on the floor of his laboratory, but what was more serious: he was no longer able to distinguish red from green. He remembered that during his experiment the bacteria in a dish were always separated according to their color (which was red or green), so that one could draw a straight line dividing them into two groups - one with all the red bacteria and the other with all the green ones.
Kleofásh is now in a big trouble since he has to separate red bacteria from green ones by a straight rod. The only way that he can find out the color of a given bacterium is to ask his colleague. In our case, the colleague will be substituted by the IPSC on-line judge.
Your task is simple: for positions of all bacteria given as an input data set, find a straight line that divides bacteria into a red group and a green group. To make this task easier, we allow a small number of bacteria of one color to be on the wrong side of this line. More precisely, the misplaced bacteria may constitute at most 2% of all bacteria. You may assume that:
As mentioned above, you will use the IPSC on-line judge instead of a colleague to determine colors of some single bacteria. In each of your submissions, you can make a guess for the dividing-line and ask for the color of any 3 bacteria. There are three possible responses:
The first response means that the guessed dividing line was correct in the sense above. The second response means that your guess for the line was incorrect, and you are given the respective colors of bacteria P, Q and R. Letters P, Q and R stand for the numbers from your submission (look at the output file description). The last response means that the format of your submission was incorrect - the judge does not know what you are asking for. Remember that you have only 10 guesses for each input, and note that "Syntax error" also counts.
The input file contains a positive integer N on the first line, specifying the number of bacteria. The following N lines contain positions of bacteria (X, Y) as two floating point values separated by a single space.
The output file contains both your guess for the dividing line and a request for the color of any 3 bacteria. The first line of the output file contains a guess in the form X1 Y1 X2 Y2, where all values are floating-point reals with up to 6 fractional digits, separated by single spaces, and specifying two distinct points on the guessed dividing line. The second line contains a request of the form P Q R, where all values are positive integers separated by single spaces and specifying the indices of bacteria in the input file (the first bacterium has index 1). You must always conform to this specification, even when guessing the correct dividing line or when you do not want the colors of all 3 bacteria (use any correct indices in this case).
7 3 2.3 7 4 1.5 1.5 5 6 2 8.5 1 4 3 5
Output file:
2.3 3.7 8 3.7 6 1 7
Colors of bacteria 6, 1 and 7 are Red, Red and Green.The guessed line (horizontal line with y=3.7) was not correct since there is one misplaced bacterium 6. This constitutes 14.3%, which is more than the allowed 2%.