在 Algorithm Association 举办的活动中，参与者可以获得近乎无限的柠檬茶。为了储存如此大量的柠檬茶，Rikka 想要建造一些仓库。

Rikka 计划建造 $N = 2^n - 1$ 个仓库，以及 $N - 1$ 条双向道路。第 $i$ 条道路连接第 $(i+1)$ 个仓库和第 $\lfloor \frac{i}{2} \rfloor$ 个仓库。

这些仓库将建在一块不平坦的土地上。对于每个 $i \in [\lceil \frac{N}{2} \rceil, N]$，第 $i$ 个仓库的海拔高度 $a_i$ 是已知的。Rikka 可以任意选择其他仓库的海拔高度。（海拔高度可以是任何实数）。

在陡峭的山坡上搬运柠檬茶非常困难。Rikka 希望使道路系统尽可能方便。因此，Rikka 想要最小化每条道路海拔高度差的平方和，即：

$$ans = \min_{a_1, \dots, a_{\lceil \frac{N}{2} \rceil - 1} \in \mathbb{R}} \sum_{i=1}^{N-1} \left(a_{i+1} - a_{\lfloor \frac{i}{2} \rfloor}\right)^2$$

由于地壳运动，最后 $\lceil \frac{N}{2} \rceil$ 个仓库的海拔高度经常发生变化。幸运的是，Rikka 可以随时免费更改前 $\lceil \frac{N}{2} \rceil - 1$ 个仓库的海拔高度。

你的任务是帮助 Rikka 在每次变化后找出最优方案。

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 18, 0 \le m \le 2 \times 10^5$)。

第二行包含 $\lceil \frac{N}{2} \rceil$ 个整数 $h_i$ ($1 \le h_i \le 10^8$)，依次表示 $a_{\lceil \frac{N}{2} \rceil}, \dots, a_N$，其中 $N = 2^n - 1$。

接下来 $m$ 行，每行包含两个整数 $x_i, w_i$ ($\lceil \frac{N}{2} \rceil \le x_i \le N, 1 \le w_i \le 10^8$)，表示在第 $i$ 次变动中，第 $x_i$ 个仓库的海拔高度变为 $w_i$。

输出格式

输出 $m + 1$ 行，每行一个数字：初始的 $ans$ 值，以及每次变动后的 $ans$ 值。

编写特殊判题程序是一项繁琐的任务。因此，你需要输出答案对 $998244353$ 取模的结果。形式化地，如果 $ans$ 的最简分数表示为 $\frac{x}{y}$，你需要输出 $x \times y^{998244351} \pmod{998244353}$。

样例

输入 1

2 0
1 3

输出 1

2

输入 2

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

输出 2

332748120
83187032
748683270
0

说明

对于第一个样例，一种最优解是 $a_1 = 2$，此时 $ans$ 的值为 $(2 - 1)^2 + (2 - 3)^2 = 2$。