조커의 카드 마술

조커는 수학이 필요한 새 카드 마술을 준비한다. 계산을 도와주자.

0이 아닌 정수 $a_i$가 적힌 카드 $n$장이 한 줄로 놓여 있다. 양수의 합을 $P$, 음수의 합을 $N$이라고 하자. 카드 $i$의 무게 $w_i$는 $a_i > 0$이면 $a_i / P$, $a_i < 0$이면 $a_i / |N|$이다.

$s_i = \sum_{j=1}^{i} w_j$로 두자. 조커는 $s_i$가 가장 큰 위치 $i$를 알고 싶다. 그런 $i$가 여러 개면 가장 작은 것을 고른다.

배열이 고정된 마술은 지루하다. 조커는 카드에 적힌 수를 바꾸고, 한 번 바꿀 때마다 $s_i$가 가장 큰 위치를 다시 알고 싶어 한다.

첫째 줄에 카드의 수 $n$과 변경 횟수 $m$이 주어진다 ($1 \le n, m \le 50000$).

둘째 줄에 처음 카드에 적힌 정수 $a_i$가 $n$개 주어진다 ($-10^9 \le a_i \le 10^9$, $a_i \ne 0$).

다음 $m$개 줄에 정수 $p_i$와 $v_i$가 하나씩 주어진다. 위치 $p_i$에 있는 카드의 수가 $v_i$로 바뀐다는 뜻이다 ($1 \le p_i \le n$, $-10^9 \le v_i \le 10^9$, $v_i \ne 0$).

어느 순간에도 양수가 적힌 카드와 음수가 적힌 카드가 각각 한 장 이상 있다. 양수의 합은 $10^9$을 넘지 않고, 음수의 절댓값의 합도 $10^9$을 넘지 않는다.

$m+1$개 줄을 출력한다.

첫째 줄에는 처음 수열에서 $s_i$가 가장 큰 위치를 출력한다. 이어지는 $m$개 줄에는 각 변경 직후 $s_i$가 가장 큰 위치를 한 줄에 하나씩 출력한다.