题目描述

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 \le n , m \le 50 000)$ .

The second line consists of $n$ integers $a_{i}$ -- numbers written on cards at the beginning $(−10^{9} \le a_{i} \le 10^{9}; 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 \le p_{i} \le n$ ; $−10^{9} \le v_{i} \le 10^{9}; 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^{9}$ and the sum of all negative cards will never exceed $−10^{9}.$

输出格式

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.

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

提示

Time limit: 3 s, Memory limit: 512 MB.