Problem I
Daily Division

Photo by biskyt30.

Oostende Beach is a very long beach located in the north of Belgium. On this beach, there are $n$ huts located along a straight line. People can rent a room in one of those huts to spend their beach vacations together with the other tenants.

Every day at lunch time, a food truck drives by to serve fries to the guests. The truck parks in front of one of the huts and people form two queues. The people staying in huts to the left of the food truck queue on the left, and the people to the right of the food truck queue on the right. The people staying in the hut in front of the food truck split their group in half, one half going to the left queue and the other half going to the right queue. If this is an odd number of people, the remaining person will go to the queue with fewer people, or choose one randomly if the queues have the same length. The food truck always positions itself so that the difference between the number of people in the left queue and the number of people in the right queue is as small as possible.

Each night the number of guests in exactly one of the huts changes. Can you help the food truck find the best position for each day?

Input

• The first line of the input consists of two integers $1\leq n \leq 10^5$, the number of huts, and $1\leq q\leq 10^5$, the number of days.

• The second line has $n$ integers $a_0$, $\dots $, $a_{n-1}$ satisfying $1\leq a_ i \leq 10^6$ for $0\leq i < n$, where $a_ i$ is the current number of people in hut $i$.

• Then follow $q$ lines with two integers $0\leq i<n$ and $1\leq x \leq 10^6$. The $j^\textrm {th}$ of these lines indicates that at day $j$ the number of people in hut $i$ changes to $x$.

Output

• Print $q$ lines: the optimal position of the food truck after each of the $q$ nights. If there are multiple optimal positions, print the smallest one.

5 4
3 1 3 4 2
0 5
0 9
4 5
2 1

2
1
2
1

4 8
1 1 1 1
2 2
1 2
2 1
1 1
3 2
2 2
1 2
2 1

1
1
1
1
1
2
2
2