There is a very large square in Stone Age. People are entering and leaving the square very frequently. When there is a tribe whose number of people in the square is strictly larger than the number of other people in the square, we say that tribe is dangerous.
Your task is to keep checking whether there is a dangerous tribe.
Your program should read from standard input, and write to standard output. After printing each line to the standard output, you should flush the output, by calling fflush(stdout) or cout << flush in C/C++, flush(output) in Pascal and System.out.flush() in Java. Please read general instructions for interactive problems for more information.
There is only one test case. Keep using Getjob command to read an integer v per line, until v=-2 (see below). There will be no more than 50000 jobs.
| v | Meaning |
| 0 | New event: There is a person entered the square. People are numbered 1, 2, ... in the same order as they enter the square. |
| >0 | New event: The person numbered v left the square. |
| -1 | You need to check whether there is a dangerous tribe and tell us the result with an Answer command. |
| -2 | The test case is finished. |
You should issue an Answer command exactly once for each v=-1, and after each new event (v>=0), you can issue Query commands to gather information. You should not issue any Query command after v=-1 (you need to Answer immediately).
| Command | Description |
| Getjob | Returns the next v. See the table above. When v=-2, the test case is finished. |
| Query i j | Returns s, whether person i and person j belongs to the same tribe. Both i and j must have entered the square. (They can be already gone, though). |
| Answer i | Tells us whether there is a dangerous tribe. i=0 means there is no dangerous tribe, otherwise person i must be still in the square, and his tribe is dangerous. This command does not return anything. |
If your program violated any of these rules (bad format, invalid arguments etc), the server will exit immediately, and you will receive Protocol Violation (PV).
After each new event, you can issue at most 5 Query commands, otherwise you'll get Protocol Limit Exceeded (PLE).
Getjob
0
Getjob
0
Query 1 2
0
Getjob
-1
Answer 0
Getjob
0
Query 2 3
1
Getjob
-1
Answer 2
Getjob
2
Getjob
-1
Answer 0
Getjob
1
Getjob
-2
In the example above, their tribe ID for each person is: 1, 2, 2.