CF992E.Nastya and King-Shamans

Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that at every moment there was exactly one shaman in Byteland, and there were n shamans in total enumerated with integers from 1 to n in the order they lived. Also, each shaman had a magic power which can now be expressed as an integer.

The chronicle includes a list of powers of the n shamans. Also, some shamans can be king-shamans, if they gathered all the power of their predecessors, i.e. their power is exactly the sum of powers of all previous shamans. Nastya is interested in whether there was at least one king-shaman in Byteland.

Unfortunately many of the powers are unreadable in the list, so Nastya is doing the following:

• Initially she supposes some power for each shaman.
• After that she changes the power of some shaman q times (the shamans can differ) and after that wants to check if there is at least one king-shaman in the list. If yes, she wants to know the index of any king-shaman.

Unfortunately the list is too large and Nastya wants you to help her.

娜斯佳喜欢读书，有时甚至一整天都待在图书馆里。今天，她在图书馆发现了一本比特兰编年史，其中记载着很久以前那里曾居住着一些萨满。众所周知，比特兰在任意时刻都恰好只有一位萨满，总共有 $n$ 位萨满，按其生存顺序用 $1$ 到 $n$ 的整数编号。此外，每位萨满都拥有一种魔法力量，如今可用一个整数来表示。

这本编年史中列出了这 $n$ 位萨满的力量值。此外，某些萨满可能成为“王萨满”：当某位萨满聚集了其所有前辈的力量时，即其力量值恰好等于所有先前萨满力量值之和，该萨满即为王萨满。娜斯佳很想知道比特兰历史上是否至少出现过一位王萨满。

不幸的是，列表中许多力量值已模糊不清，因此娜斯佳采取如下做法：

• 最初，她为每位萨满假设一个力量值；
• 随后，她对某位萨满的力量值进行 $q$ 次修改（每次修改的对象可以不同）；每次修改后，她希望检查当前列表中是否至少存在一位王萨满；若存在，则她希望知道任意一位王萨满的编号（即下标）。

不幸的是，这份列表规模过大，娜斯佳希望你能帮助她。

The first line contains two integers n and q (1 ≤ n, q ≤ 2·105).

The second line contains n integers _a_1, ..., a__n (0 ≤ a__i ≤ 109), where a__i is the magic power of the i-th shaman.

After that q lines follow, the i-th of them contains two integers p__i and x__i (1 ≤ p__i ≤ n, 0 ≤ x__i ≤ 109) that mean that the new power of the p__i-th shaman is x__i.

第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 2·10^5$）。

第二行包含 $n$ 个整数 $a_1, ..., a_n$（$0 ≤ a_i ≤ 10^9$），其中 $a_i$ 表示第 $i$ 位萨满的魔法力量。

随后是 $q$ 行，其中第 $i$ 行包含两个整数 $p_i$ 和 $x_i$（$1 ≤ p_i ≤ n$, $0 ≤ x_i ≤ 10^9$），表示第 $p_i$ 位萨满的新力量值为 $x_i$。

Print q lines, the i-th of them should contain  - 1, if after the i-th change there are no shaman-kings, and otherwise a single integer j, where j is an index of some king-shaman after the i-th change.

If there are multiple king-shamans after each change, print the index of any of them.

输出 q 行，其中第 i 行应包含  - 1（若在第 i 次修改后不存在“萨满王”），否则为一个整数 j，其中 j 是某一位“萨满王”的下标。

每次修改后若存在多个“萨满王”，则输出其中任意一个的下标即可。

In the first example powers of shamans after the first change are equal to (2, 3). The answer equals  - 1, because the sum of powers of shamans before the first shaman is equal to 0, and before the second is equal to 2.

In the second example after the first change the powers are equal to (1, 2, 3). The answer is equal to 3, because the power of the third shaman is equal to 3, and the sum of powers of the first and the second shaman is also 1 + 2 = 3. After the second change the powers become equal to (2, 2, 3), where the answer equals 2. After the third change the powers become equal to (2, 4, 3), where the answer equals  - 1. After the fourth change the powers become equal to (2, 4, 6), where the answer equals 3.

在第一个例子中，第一次修改后萨满的力量值为 $(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$。