Problem Statement

Given are a sequence of $N$ positive integers $A = (A_1, A_2, \ldots, A_N)$ and $Q$ queries. The $i$-th query is as follows:

• given integers $x_i$ and $y_i$ (where $1\leq x_i\leq N$), change $A_{x_i}$ to $y_i$.

Each time the query changes the sequence, find the answer to the following problem modulo $998244353$ (see Notes).

Let $f(n)$ be the maximum total number of points when doing the following operation $n$ times on $A$.

• Choose $i, j$ such that $A_i\leq A_j$ and choose non-negative real number $x$ such that $A_i + 2x \leq A_j$.
• Add $x$ to $A_i$ and subtract $x$ from $A_j$.
• Gain $x$ points.

It can be proved that the limit $\displaystyle \lim_{n\to\infty} f(n)$ exists. Find this limit.

Note

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R\times Q\equiv P\pmod{998244353}$ and $0\leq R < 998244353$. Find this $R$.

Constraints

• $2\leq N\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• $1\leq A_i \leq 10^9$
• $1\leq x_i\leq N$
• $1\leq y_i\leq 10^9$

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
x_1 y_1
\vdots
x_Q y_Q

Output

Print $Q$ lines; the $i$-th line should contain the answer to the problem just after the change by the $i$-th query.