Description

On an infinitely long road, there is an infinite row of street lamps, numbered $1, 2, 3, 4, \dots$.

Each lamp has two possible states: on or off. If you press the switch of a lamp once, its state toggles. If it was on, it turns off. If it was off, it turns on.

Initially, all lamps are off. Each time, Xiao Ming can perform the following operation:

Specify two numbers, $a, t$ ($a$ is a real number, $t$ is a positive integer). Press once the switches of the lamps numbered $\lfloor a \rfloor, \lfloor 2 \times a \rfloor, \lfloor 3 \times a \rfloor, \dots, \lfloor t \times a \rfloor$. Here $\lfloor k \rfloor$ denotes the integer part of the real number $k$.

After Xiao Ming has performed $n$ such operations, he suddenly discovers that exactly one lamp is on. He wants to know the index of this lamp, but it is too far away for him to read the number.

Fortunately, Xiao Ming still remembers the previous $n$ operations. He turns to you for help. Can you compute the index of the lamp that is on?

Input Format

The first line contains a positive integer $n$, the number of operations.

The next $n$ lines each contain two numbers, $a_i, t_i$. Here $a_i$ is a real number with exactly $6$ digits after the decimal point, and $t_i$ is a positive integer.

Output Format

Output a single positive integer: the index of the lamp that is on.

3
1.618034 13
2.618034 7
1.000000 21

20

Hint

Let $T=\sum \limits_{i=1}^n t_i = t_1+t_2+t_3+\dots+t_n$.

• For 30% of the testdata, $T \le 1000$.
• For 80% of the testdata, $T \le 200000$.
• For 100% of the testdata, $T \le 2000000$.
• For 100% of the testdata, $n \le 5000$, $1 \le a_i < 1000$, $1 \le t_i \le T$.

It is guaranteed by the testdata that after $n$ operations, there is exactly one lamp that is on, so you do not need to handle invalid cases. Also, for all $i$, the maximum value of $t_i \times a_i$ does not exceed $2000000$.

Translated by ChatGPT 5