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

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

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: