На секретном оборонном заводе трудятся N рабочих.
Каждый рабочий характеризуется своей производительностью — целым числом.
С течением времени производительность некоторых рабочих может увеличиваться
или уменьшаться. Вам задано число M — количество изменений производительности.
Для каждого изменения известен номер рабочего, изменившего свою производительность
и значение, на которое он она изменилась.
Величина изменения может быть как положительной, так и отрицательной.
Для планирования будущих достижений руководству завода необходимо всегда
знать наибольшую производительность, достигнутую рабочими в данный момент.
Формат входного файла
В первой строке входного файла содержатся целые числа N M, разделенные пробелами.
Далее следуют N чисел Ai, обозначающих производительность i-рабочего.
Завершают входной файл M пар чисел Numi Vali, обозначающие
номер рабочего, производительность которого изменилась и величину изменения соответственно.
Формат выходного файла
В выходной файл необходимо вывести M чисел —
после каждого изменения производительности необходимо вывести
наибольшую производительность по заводу.
Ограничения
(1 ≤ N, M ≤ 100000,
1 ≤ Numi ≤ N,
−1000 ≤ Vali, Ai ≤ 1000)
