Настя любит читать, и иногда целые дни проводит в библиотеке. Сегодня она нашла там летопись Байтландии, в которой написано, что когда-то в Байтландлии жили шаманы. Известно, что в каждый момент времени в Байтландии всегда был ровно один шаман, а всего за всю историю шаманов было n, и они были пронумерованы различными целыми числами от 1 до n так, что каждый следующий по номеру шаман был после предыдущего. Также у каждого шамана есть магическая сила, выражающаяся целым числом.
В летописи приведен список сил n главных шаманов Байтландии. Также существуют шаманы-короли. Шаман называется шаманом-королем, если к нему передалась сила всех предков, то есть если его магическая сила в точности равна сумме магических сил предыдущих шаманов. Теперь Насте стало интересно, жил ли когда-нибудь в Байтландии шаман-король.
К сожалению, многие записи стерлись, и однозначно их восстановить невозможно. Поэтому Настя делает следующее:
- Изначально она восстанавливает силы всех шаманов каким-то образом.
- Затем она q раз меняет восстановленную силу какого-то одного шамана (но не обязательно каждый раз одного и того же) и после каждого изменения хочет узнать, есть ли среди шаманов король. Если шаман-король есть, то Настя хочет знать номер любого из них.
К сожалению, летопись очень большая, поэтому Настя попросила вас помочь.
Выходные данные
Выведите q строк, i-я из которых содержит - 1, если после i-го изменения шамана-короля не существует, а иначе содержит одно число j, где j — индекс шамана-короля после i-го изменения.
Если после некоторого изменения есть несколько королей-шаманов, выведите индекс любого из них.
Примечание
В первом примере после изменения силы шаманов равны (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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 3
1 2
|
-1
|
|
2
|
3 4
2 2 3
1 1
1 2
2 4
3 6
|
3
2
-1
3
|
|
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
|