F. Thanos Sort
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Thanos sort is one of the sorting algorithms that works in time linear in the length of the array.

The sorting algorithm is as follows:

1) If the array $$$a = (a_1, \cdots , a_n)$$$ is already sorted, then the process stops. An array is considered sorted if for every $$$i$$$ from $$$2$$$ to $$$n$$$, it holds that $$$a_{i-1} \le a_i$$$.

2) Otherwise, either the first $$$\lceil \frac{n}{2} \rceil$$$ elements of the array or the last $$$\lfloor \frac{n}{2} \rfloor$$$ elements are chosen uniformly at random. All of them are removed, and the algorithm proceeds to step 1.

For example, sorting the array $$$[10, 4, 5, 6, 8]$$$ may look as follows:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[6, 8]$$$

Or:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[10, 4, 5]$$$ -> $$$[10, 4]$$$ -> $$$[10]$$$

Since many elements may disappear during Thanos sort, for an array $$$a$$$, let $$$f(a)$$$ be the expected number of elements remaining in the final array.

You are given some array $$$a$$$.

You need to process the following queries:

$$$i, x$$$ – assign $$$a_i := x$$$.

After each query, you need to output $$$f(a)$$$ for the current array.

Input

The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 10^6$$$) – the length of the array and the number of queries, respectively.

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

Each of the next $$$q$$$ lines contains a pair of integers $$$i, x$$$ ($$$1 \le i \le n, 0 \le x \le 10^9$$$) – the parameters of the next query.

Output

After each query, output $$$f(a)$$$ modulo $$$998244353$$$ on a separate line.

Example
Input
5 8
10 4 5 6 8
1 5
5 0
3 3
2 11
4 7
3 12
5 17
4 13
Output
499122178
1
1
748683266
748683266
2
499122179
5