E. Настя и шаманы-короли
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Настя любит читать, и иногда целые дни проводит в библиотеке. Сегодня она нашла там летопись Байтландии, в которой написано, что когда-то в Байтландлии жили шаманы. Известно, что в каждый момент времени в Байтландии всегда был ровно один шаман, а всего за всю историю шаманов было n, и они были пронумерованы различными целыми числами от 1 до n так, что каждый следующий по номеру шаман был после предыдущего. Также у каждого шамана есть магическая сила, выражающаяся целым числом.

В летописи приведен список сил n главных шаманов Байтландии. Также существуют шаманы-короли. Шаман называется шаманом-королем, если к нему передалась сила всех предков, то есть если его магическая сила в точности равна сумме магических сил предыдущих шаманов. Теперь Насте стало интересно, жил ли когда-нибудь в Байтландии шаман-король.

К сожалению, многие записи стерлись, и однозначно их восстановить невозможно. Поэтому Настя делает следующее:

  • Изначально она восстанавливает силы всех шаманов каким-то образом.
  • Затем она q раз меняет восстановленную силу какого-то одного шамана (но не обязательно каждый раз одного и того же) и после каждого изменения хочет узнать, есть ли среди шаманов король. Если шаман-король есть, то Настя хочет знать номер любого из них.

К сожалению, летопись очень большая, поэтому Настя попросила вас помочь.

Входные данные

В первой строке входного файла содержится два числа 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-го изменения.

Если после некоторого изменения есть несколько королей-шаманов, выведите индекс любого из них.

Примеры
Входные данные
2 1
1 3
1 2
Выходные данные
-1
Входные данные
3 4
2 2 3
1 1
1 2
2 4
3 6
Выходные данные
3
2
-1
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
Выходные данные
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.