Joker's Card Trick

Joker is preparing a new card trick that needs some arithmetic. Help him with the calculation.

A row holds $n$ cards, and card $i$ carries a nonzero integer $a_i$. Let $P$ be the sum of all positive numbers in the row, and let $N$ be the sum of all negative numbers. Card $i$ has weight $w_i = a_i / P$ when $a_i > 0$, and $w_i = a_i / |N|$ when $a_i < 0$.

Let $s_i = \sum_{j=1}^{i} w_j$. Joker wants the position $i$ with the largest $s_i$. If several positions give that largest value, he takes the smallest one.

A trick with a fixed row is boring. Joker changes the numbers written on the cards, and after every change he wants the position with the largest $s_i$ again.

The first line contains two integers $n$ and $m$, the number of cards and the number of changes ($1 \le n, m \le 50000$).

The second line contains $n$ integers $a_i$, the numbers written on the cards at the start ($-10^9 \le a_i \le 10^9$, $a_i \ne 0$).

Each of the next $m$ lines contains two integers $p_i$ and $v_i$, meaning that the number on the card at position $p_i$ becomes $v_i$ ($1 \le p_i \le n$, $-10^9 \le v_i \le 10^9$, $v_i \ne 0$).

At every moment the row contains at least one card with a positive number and at least one card with a negative number. The sum of the positive numbers never exceeds $10^9$, and the sum of the absolute values of the negative numbers never exceeds $10^9$.

Print $m+1$ lines.

On the first line print the position with the largest $s_i$ for the initial numbers. On each of the following $m$ lines print the position with the largest $s_i$ right after the corresponding change, one position per line.