Joker's Card Trick Calculation

Joker has prepared a new card trick with a strong mathematical background. There is a row of n cards with non-zero numbers a_i written on them. Define P as the sum of all positive numbers and N as the sum of all negative numbers. The weight of each card is defined as follows:

\(w_i = \begin{cases}\frac{a_i}{P} & \text{if } a_i > 0,\\[6pt]\frac{a_i}{|N|} & \text{if } a_i < 0.\end{cases}\)

Let \(s_i = \sum_{j=1}^{i} w_j\) be the prefix sum of weights. Joker wants to know the positive index i which maximizes \(s_i\). If there is more than one such index, choose the smallest one.

However, the trick is dynamic: after some updates (i.e. changing the number on a card), you need to perform the calculation again. After each update, report the index with the largest \(s_i\).

inputFormat

The first line contains two integers n and q (number of cards and number of updates). The second line contains n nonzero integers representing the initial values on the cards. Each of the next q lines contains two integers: an index i (1-indexed) and a new value, indicating that the number on the i-th card is changed to the new value.

outputFormat

For each update, output a single integer (on a separate line) representing the index (1-indexed) with the largest prefix sum \(s_i\) after the update. If multiple indices share the same maximum value, output the smallest index.

sample

3 1
5 -3 2
2 -1

1