B. Aquarium Bubble Lights
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ operations. The $$$t$$$-th operation consists of the following steps in order:

  1. For every $$$i$$$ ($$$1 \le i \le n$$$), replace $$$a_i$$$ with $$$\max(a_i - 1, 0)$$$.
  2. Given two integers $$$x_t$$$ and $$$v_t$$$, if $$$x_t \ne 0$$$, replace $$$a_{x_t}$$$ with $$$\max(a_{x_t}, v_t)$$$. If $$$x_t = 0$$$, the sequence is not changed in this step.

After each operation, find the number of positive elements in the sequence. After all operations, also find the final sequence.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), the initial sequence.

Each of the next $$$q$$$ lines contains two integers $$$x_t$$$ and $$$v_t$$$ ($$$0 \le x_t \le n$$$, $$$0 \le v_t \le 10^9$$$), describing the $$$t$$$-th operation. It is guaranteed that $$$v_t = 0$$$ if $$$x_t = 0$$$.

Output

After each operation, print a single integer — the number of positive elements in the sequence.

After all operations, print one line containing $$$n$$$ integers — the final sequence.

Example
Input
4 5
2 0 5 1
2 3
3 2
0 0
1 4
2 0
Output
3
2
2
2
1
3 0 0 0
Note

After the first step of the first operation, the sequence is $$$[1, 0, 4, 0]$$$. Then the second element becomes $$$\max(0, 3) = 3$$$, so the sequence is $$$[1, 3, 4, 0]$$$ and it has $$$3$$$ positive elements.

The first step is always performed before the second step of the same operation.