시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 2 2 100.000%

문제

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 ai 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 wi = ai/P if ai > 0 and ai/|N| otherwise.

Let’s denote si = \(\sum_{j=1}^{j \le i}{w_j}\). Joker needs to know positive i with the largest si. 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 si 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 ai — numbers written on cards at the beginning (−109 ≤ ai ≤ 109; ai ≠ 0).

The following m lines contain two integers each: pi and vi, that means value of card at position pi is changed to vi (1 ≤ pi ≤ n; −109 ≤ vi ≤ 109; vi ≠ 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 109 and the sum of all negative cards will never exceed −109.

출력

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

예제 입력

4 7
1 -5 3 -5
4 -1
2 -1
3 10
4 10
1 -1
2 1
3 -1

예제 출력

3
1
3
3
1
4
4
4

힌트