Trong một cuộc thí nghiệm tự hỏi tự trả lời do Lợi tổ chức, có ~n~ kẹo thủ được đánh thứ tự ~1~ đến ~n~ từ trái qua phải. Mỗi kẹo thủ đang có ~a_i~ kẹo. Một kẹo thủ được gọi là vua kẹo, nếu số kẹo của anh ta chính xác bằng tổng số kẹo của các kẹo thủ bên trái. Lợi quan tâm đến việc liệu có ít nhất một vua kẹo hay không.
Thí nghiệm như sau, Lợi thực hiện ~q~ thay đổi. Với mỗi thay đổi:
-
Lợi chọn kẹo thủ ~p_i~ và thay đổi số kẹo của anh ta thành ~x_i~.
-
Kiểm tra xem có ít nhất một vua kẹo hay không. Nếu có, Lợi muốn biết chỉ số của một vua kẹo bất kỳ.
Do Lợi hay bị lag, nên các bạn hãy giúp anh ấy nhé.
Input
Dòng đầu chứa ~n~ và ~q~ (~1 le n, q le 2 times 10^5~).
Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, cdots, a_n~ (~0 le a_i le 10^9~) – số kẹo của các kẹo thủ.
Cuối cùng là ~q~ dòng, dòng thứ ~i~ chứa ~p_i~ và ~x_i~ (~1 le p_i le n~, ~0 le x_i le 10^9~) – thay đổi thứ ~i~.
Output
In ra ~q~ dòng, dòng thứ ~i~ chứa ~-1~, nếu sau thay đổi thứ ~i~, không có vua kẹo nào. Ngược lại in ra ~j~ là chỉ số của vua kẹo.
Nếu có nhiều vua kẹo sau thay đổi, in ra chỉ số của vua kẹo bất kỳ.
Sample Input 1
2 1 1 3 1 2
Sample Output 1
-1
Sample Input 2
3 4 2 2 3 1 1 1 2 2 4 3 6
Sample Output 2
3 2 -1 3
Sample Input 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
Sample Output 3
1 -1 9 -1 4 -1 1
Notes
Ở ví dụ đầu tiên, số kẹo của các kẹo thủ sau thay đổi thứ nhất là (~2, 3~). Đáp án là ~-1~, vì tổng số kẹo của các kẹo thủ bên trái kẹo thủ thứ nhất là ~0~, bên trái kẹo thủ thứ hai là ~2~.
Ở ví dụ thứ hai:
-
Sau thay đổi thứ nhất, số kẹo của các kẹo thủ là (~1, 2, 3~). Đáp án là ~3~, vì kẹo thủ thứ ba có ~3~ kẹo, tổng số kẹo của kẹo thủ thứ nhất và thứ hai cũng là ~1 + 2 = 3~.
-
Sau thay đổi thứ hai, số kẹo là (~2, 2, 3~), đáp án là ~2~.
-
Sau thay đổi thứ ba, số kẹo là (~2, 4, 3~), đáp án là ~-1~.
-
Sau thay đổi thứ tư, số kẹo là (~2, 4, 6~), đáp án là ~3~.
