时空限制

3S/1024M

题目描述

jiangly 出了一场数数场后，发现大家很不擅长做数数题，于是 jiangly 决定在大赛中多放些数数题来难倒大家。

由 jiangly 出题的大赛一共有 $n$ 道题，第 $i$ 道题可能是数数题，也可能不是。

由于大家十分讨厌数数题，尤其是连续的数数题。因此为了不让大家彻底崩溃，jiangly 规定：不能出现连续 $k+1$ 道（或更多）的数数题。

大家在看到大赛题目后，会从第 $1$ 题到第 $n$ 题按顺序浏览一遍。大家初始的“不满意度”为 $1$。

在浏览过程中，如果遇到第 $i$ 道题是数数题，并且它恰好是当前连续出现的第 $t$ 道数数题，那么大家的不满意度就会乘以 $a_{i,t}$。（如果第 $i$ 道题不是数数题，则连续计数清零，不满意度不变）。

jiangly 希望求出在所有合法的出题方案中，大家最终“不满意度”的总和。由于答案可能很大，需要对 $998244353$ 取模。

但是，大家对于数数题的厌恶程度会随着时间而改变。具体来说，会发生 $q$ 次改变，每一次改变都形如：将 $a_{i,j}$ 的值修改为 $t$。 jiangly 希望在每一次修改之后，都能求出最新的所有合法方案的不满意度之和。

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，意义如题目描述所述。

接下来的 $n$ 行，每行包含 $k$ 个整数。其中第 $i$ 行的第 $j$ 个数表示初始的 $a_{i,j}$。

随后一行包含一个整数 $q$，表示修改操作的次数。

接下来的 $q$ 行，每行包含三个整数 $i$、$j$、$t$，表示将 $a_{i,j}$ 的值修改为 $t$。

输出格式

输出共 $q$ 行。每行包含一个整数，表示在对应的修改操作执行完成后，所有合法方案的不满意度之和对 $998244353$ 取模的结果。

样例

样例输入 #1

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

样例输出 #1

54
70

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^4$，$1 \leq q \leq 5\times 10^4$，$1 \le k \le 5$，$1 \le a_{i,j}, t \le 10^9$，$1 \le i \le n$，$1 \le j \le k$。