暂无测试数据。

有一个 $n\times n$ 的矩阵，左上角为 $(1,1)$，右下角为 $(n,n)$，你要从左上角走到右下角，只能向右或向下走。

矩阵的每个位置有一个权值，在走的过程中，你会获得经过的所有点上的权值，从 $(1,1)$ 走到 $(n,n)$，获得的权值之和称为这条路径的权值。你想要知道，从左上角走到右下角的所有路径的权值总和。

还有 $q$ 次修改，每次会使一个三角区域内每个位置的权值 $+c$，每次修改过后你需要输出从左上角走到右下角的所有路径的权值总和。

三角区域定义如下：

三角区域是一个等腰直角三角形，并且斜边的方向一定是从左下到右上，且三角形一定在斜边的左上方，像这样：

其中，蓝色点称为三角形的直角点。

输入格式

第一行两个整数 $n,q$。

下面 $n$ 行每行 $n$ 个整数，表示这个矩阵每个位置的初始权值。

下面 $q$ 行每行 $4$ 个整数 $x,y,len,c$，表示使直角点为 $x,y$，直角边长为 $len$ 的三角区域内每个位置的权值 $+c$。

输出格式

输出 $q$ 行，每行一个整数表示从左上角走到右下角的所有路径的权值总和对 $998244353$ 取模后的值。

数据范围

对于前 $20\%$ 的数据，有 $n,q\leq 100$。

对于前 $40\%$ 的数据，有 $n,q\leq 10^3$。

对于 $100\%$ 的数据，有 $1\leq n\leq 1.5\times 10^3,1\leq q\leq 10^6,0\leq a_{i,j},c<998244353$，其中 $a_{i,j}$ 是矩阵第 $i$ 行第 $j$ 列的初始权值，保证每次修改的三角区域不会超出矩阵。

3 1
0 1 0
1 0 1
1 1 0
2 1 2 1

21