Rikka와 창고

Algorithm Association이 여는 행사에서는 참가자들에게 레몬 티가 거의 무한히 제공된다. 이렇게 많은 레몬 티를 보관하기 위해 Rikka는 창고를 몇 개 지으려 한다.

Rikka는 $N=2^n-1$개의 창고와 $N-1$개의 양방향 도로를 지을 계획이다. $i$번째 도로는 $(i+1)$번째 창고와 $\lceil \frac{i}{2} \rceil$번째 창고를 연결한다.

이 창고들은 울퉁불퉁한 땅 위에 지어진다. 각 $i \in [\lceil \frac{N}{2} \rceil, N]$에 대해 $i$번째 창고의 고도는 $a_i$로 주어진다. 나머지 창고의 고도는 Rikka가 임의로 정할 수 있다. 고도는 임의의 실수가 될 수 있다.

가파른 언덕에서 레몬 티를 나르기는 힘들다. Rikka는 도로 체계를 최대한 편하게 만들고 싶어 한다. 따라서 각 도로 양 끝 창고의 고도 차이의 제곱합을 최소화하려 한다. 즉, $ans = \min_{a_1, \dots, a_{\lfloor \frac{N}{2} \rfloor} \in \mathbb R} \sum_{i=1}^{N-1} \left( a_{i+1} - a_{\lceil \frac{i}{2} \rceil}\right)^2$

지각 운동 때문에 마지막 $\lceil \frac{N}{2} \rceil$개 창고의 고도는 자주 바뀐다. 다행히 Rikka는 처음 $\lfloor \frac{N}{2} \rfloor$개 창고의 고도를 언제든지 자유롭게 바꿀 수 있다.

각 변화 이후의 최적 계획을 구하는 것이 Rikka의 과제이다.

첫째 줄에 두 정수 $n,m\ (2 \leq n \leq 18, 0 \leq m \leq 2 \times 10^5)$이 주어진다.

둘째 줄에 $\lceil \frac{N}{2} \rceil$개의 정수 $h_i\ (1 \leq h_i \leq 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 \leq x_i \leq n, 1 \leq w_i \leq 10^8)$가 주어진다. 이는 $i$번째 변화에서 $x_i$번째 창고의 고도를 $w_i$로 바꾼다는 뜻이다.

총 $m+1$개의 줄을 출력한다. 각 줄에는 하나의 수를 출력하며, 첫 줄에는 초기 $ans$ 값을, 그 다음 $m$개의 줄에는 각 변화 이후의 $ans$ 값을 출력한다.

특별 심사 코드를 작성하는 것은 번거로운 일이다. 따라서 답을 $998244353$으로 나눈 나머지를 출력해야 한다. 구체적으로, $ans$를 기약분수로 나타냈을 때 $\frac{x}{y}$라 하면 $x \times y^{998244351} \text{ mod } 998244353$을 출력한다.

첫 번째 예시에서 한 최적해는 $a_1=2$이고, $ans$의 값은 $(2-1)^2 + (2-3)^2 = 2$이다.