Given a sequence $A_1, \dots, A_n$ of length $n$, and $m$ operations, each operation modifies one $A_i$ to $k$. Before the first modification and after each modification, you are required to find a non-decreasing sequence $B_1, \dots, B_n$ of the same length that minimizes $\sum_{i=1}^n (A_i - B_i)^2$, and output this minimum value. Note that the effect of each operation is independent, meaning each operation only affects the current query. To avoid precision issues, we guarantee that this minimum value is a fraction, which can be represented as the division of two non-negative integers: $x/y$. You should output the value of $(x \cdot y^{P-2}) \pmod P$, representing the value of $x/y$ modulo $P$, where $P = 998244353$ is a large prime.

Input

The first line contains two non-negative integers $n$ and $m$, representing the sequence length and the number of operations. The second line contains $n$ space-separated positive integers, representing the sequence $A_1, \dots, A_n$. The next $m$ lines each contain two positive integers $i$ and $k$, representing the modification of $A_i$ to $k$.

Output

Output $m+1$ lines, each containing one integer. The $i$-th line should output the answer after the $(i-1)$-th modification. Specifically, the first line should be the answer for the initial state.

Constraints

• For the first 10% of the data, $n, m \le 10$, $A_i, k \le 1000$, and there exists an optimal solution where all $B_i$ are integers.
• For the first 30% of the data, $n, m \le 100$.
• For another 20% of the data, $m = 0$.
• For another 20% of the data, $n, m \le 3 \times 10^4$.
• For all data, $3 \le n \le 10^5$, $0 \le m \le 10^5$, $1 \le k, A_i \le 10^9$.

Examples

Input 1

5 3
9 2 4 6 4
1 1
1 4
5 6

Output 1

28
2
4
26

Note

The optimal $B$ sequence for the first query is: $\{5, 5, 5, 5, 5\}$. The optimal $B$ sequence for the second query is: $\{1, 2, 4, 5, 5\}$. The optimal $B$ sequence for the third query is: $\{3, 3, 4, 5, 5\}$. The optimal $B$ sequence for the fourth query is: $\{5, 5, 5, 6, 6\}$. The example represents a special case where there exists an optimal solution such that all $B_i$ are integers.