Nastya 喜欢阅读,有时甚至会在图书馆待上一整天。今天她在图书馆里发现了一本拜特兰的编年史,上面写着很久以前就生活着萨满。众所周知,在Byteland中每一时刻都只有一个萨满,总共有n个萨满,按照他们居住的顺序从1到n的整数进行列举。此外,每个萨满都有魔力,现在可以用整数表示。
编年史包括 n 个萨满的力量列表。另外,有些萨满可以成为国王萨满,如果他们聚集了前任萨满的所有力量,即他们的力量恰好是所有先前萨满的力量之和。娜斯佳对拜特兰是否至少有一位国王萨满感兴趣。
不幸的是,列表中的许多能力是不可读的,因此 Nastya 正在执行以下操作:
- 最初她认为每个萨满都有一些力量。
- 之后她改变了一些萨满的力量q次(萨满可以不同),之后想要检查列表中是否至少有一个国王萨满。如果是的话,她想知道任何国王萨满的索引。
不幸的是,这个列表太大了,Nastya 希望你帮助她。
输入
第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 2·105)。
第二行包含n个整数a1, ..., an (0 ≤ ai ≤ 109),其中ai是第i个萨满的魔力。
接下来是q行,其中第i行包含两个整数pi和xi(1≤pi≤n,0≤xi≤109),这意味着第pi个萨满的新力量是xi。
输出
打印 q 行,其中第 i 行应包含 - 1,如果在第 i 次更改后没有萨满国王,否则为单个整数 j,其中 j 是第 i 次更改后某个萨满国王的索引。
如果每次更改后有多个国王萨满,则打印其中任何一个的索引。
示例
输入 #1
2 1 1 3 1 2
输出 #1
-1
输入 #2
3 4 2 2 3 1 1 1 2 2 4 3 6
输出 #2
3 2 -1 3
输入 #3
10 7 0 3 1 4 6 2 7 8 10 1 2 5 1 3 9 36 4 10 4 9 1 2 1 0
输出 #3
1 -1 9 -1 4 -1 1
注意
在第一个示例中,第一次更改后萨满的力量等于 (2, 3)。答案等于 - 1,因为第一个萨满之前的萨满力量总和等于 0,第二个萨满之前的萨满力量总和等于 2。
在第二个示例中,第一次更改后的幂等于 (1, 2, 3)。答案等于 3,因为第三个萨满的力量等于 3,第一个和第二个萨满的力量之和也是 1 + 2 = 3。第二次更改后,力量变为等于 (2, 2, 3),其中答案等于 2。第三次更改后,力量变为等于 (2, 4, 3),其中答案等于 - 1。第四次更改后,力量等于(2, 4, 6),其中答案等于 3。