Description

Joker 准备了一种新的纸牌戏法，具有强烈的数学背景。你被要求帮助 Joker 进行计算。

有一排 $n$ 张牌，上面写着非零数字 $a_{i}$。我们称所有正数的和为 $P$，所有负数的和为 $N$。每张牌 $i$ 的权重为 $w_{i} = a_{i}/P$ 如果 $a_{i} > 0$，否则为 $a_{i}/|N|$。

我们用 $s_{i} = ( \sum_{j=1}^{j \le i}{w_j})$ 表示。Joker 需要知道使 $s_{i}$ 最大的正整数 $i$。如果有多个这样的 $i$，他对最小的一个感兴趣。

但静态的戏法很无聊，所以 Joker 想要改变一些牌上的数字，并且在每次改变后，他需要知道最大的 $s_{i}$ 在哪里。

Input Format

输入的第一行包含两个整数 $n$ 和 $m$ —— 牌的数量和变化的次数 $(1 \le n , m \le 50 000)$。

第二行包含 $n$ 个整数 $a_{i}$ —— 初始时牌上写的数字 $(-10^{9} \le a_{i} \le 10^{9}; a_{i} eq 0)$。

接下来的 $m$ 行每行包含两个整数：$p_{i}$ 和 $v_{i}$，表示位置 $p_{i}$ 的牌的值被改为 $v_{i} (1 \le p_{i} \le n$；$-10^{9} \le v_{i} \le 10^{9}; v_{i} eq 0)$。

保证在每个时刻至少有一张牌上的数字是正的，至少有一张牌上的数字是负的。所有正数牌的和不会超过 $10^{9}$，所有负数牌的和不会超过 $-10^{9}$。

Output Format

你应该输出 $m+1$ 个整数。第一个整数是初始数字时最大的 $s_{i}$ 的位置。接下来的 $m$ 个数字是在每次变化后最大的 $s_{i}$ 的位置。

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

Hint

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。