409027: GYM103416 G Favorite Number

This problem is interactive. That means you can make queries and get responses in the online mode. Please be sure to use the stream flushing operation after each query's output in order not to leave part of your output in some buffer. For example, in C++ you've got to use the fflush(stdout) function, in Java — call System.out.flush(), and in Pascal — flush(output).

Ulzhan is a young researcher at NU. She wants to find out what number is the most popular favorite number amongst Kazakh people. But since there are millions of Kazakh people, she asked for your help. Ulzhan already has a list of people who agreed to participate in this research. Your job is to simply go through the list and ask each person what his or her favorite number is. It is guaranteed that one of the numbers appears strictly more than 50% of the time. In other words, the most popular number accounts for the majority of participant responses. Your task is to find that number after having received all the responses.

It is guaranteed that each participant's response is an integer within the range $$$[-10^{18}, 10^{18}]$$$, and the total number of participants is within the range $$$[1, 10^6]$$$.

Pay attention to the unusual time and memory constraints!

Use standard input and output for the interaction.

1. To start the interaction, output a single line consisting of a string "next".

2. Read a line of input consisting of a single integer, a participant's response.

3. Keep repeating steps 1 and 2, until you read -1 in step 2.

4. If you read -1, it means you have received all the responses. This -1 is not a participant response and should not be counted towards the answer!

5. Output a single integer, the number that appeared more than half of the times in step 2, excluding the last -1.

After step 5, your program should terminate immediately.

7
7
4
9
7
-1

next
next
next
next
next
next
7