15140번 - Joker 다국어

Joker prepares a new card trick with a strong mathematical background. You are asked to help Joker with calculations.

There is a row of n cards with non-zero numbers a_i written on them. Let’s call the sum of all positive numbers P and the sum of all negative numbers N. Every card i has a weight w_i = a_i/P if a_i > 0 and a_i/|N| otherwise.

Let’s denote s_i = \(\sum_{j=1}^{j \le i}{w_j}\). Joker needs to know positive i with the largest s_i. If there is more than one such i, he is interested in the smallest one.

But static tricks are boring, so Joker wants to change numbers on some cards, and after each change he needs to known where is the largest s_i is.

The first line of the input contains two integers n and m — the number of cards and the number of changes (1 ≤ n, m ≤ 50 000).

The second line consists of n integers a_i — numbers written on cards at the beginning (−10⁹ ≤ a_i ≤ 10⁹; a_i ≠ 0).

The following m lines contain two integers each: p_i and v_i, that means value of card at position p_i is changed to v_i (1 ≤ p_i ≤ n; −10⁹ ≤ v_i ≤ 10⁹; v_i ≠ 0).

It is guaranteed that at each moment there is at least one card with positive number and at least one card with negative number. The sum of all positive cards will never exceed 10⁹ and the sum of all negative cards will never exceed −10⁹.

You should output m+1 integers. The first integer is the position of the largest s_i for the initial numbers. Next m numbers are positions of the largest s_i after each change.