Joker 准备了一个具有深厚数学背景的新纸牌魔术。你需要帮助 Joker 进行计算。

有一排 $n$ 张卡片，上面写着非零数字 $a_i$。设所有正数的和为 $P$，所有负数的和为 $N$。每张卡片 $i$ 的权重 $w_i$ 定义为：若 $a_i > 0$，则 $w_i = \frac{a_i}{P}$；否则 $w_i = \frac{a_i}{|N|}$。

记 $s_i = \sum_{j=1}^{i} w_j$。Joker 需要知道使 $s_i$ 最大的正整数 $i$。如果存在多个这样的 $i$，他关心其中最小的一个。

静态的魔术很无聊，所以 Joker 想要改变某些卡片上的数字，并且在每次改变后，他都需要知道 $s_i$ 最大的位置在哪里。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 卡片的数量和修改的次数 ($1 \le n, m \le 50\,000$)。

第二行包含 $n$ 个整数 $a_i$ —— 初始时卡片上的数字 ($-10^9 \le a_i \le 10^9$; $a_i \neq 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 \neq 0$)。

保证在任何时刻至少有一张正数卡片和至少一张负数卡片。所有正数卡片之和永远不会超过 $10^9$，所有负数卡片之和永远不会超过 $-10^9$。

输出格式

你需要输出 $m+1$ 个整数。第一个整数是初始状态下 $s_i$ 最大的位置。接下来的 $m$ 个数字分别是每次修改后 $s_i$ 最大的位置。

样例

样例输入 1

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

样例输出 1

3
1
3
3
1
4
4
4