← 返回题目列表

Codeforces · 992/E

E. 娜斯佳和国王萨满

中文机器翻译题面 查看原题

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。