【题目描述】

有一个$H×W$的网格，从上往下第$h$行，从左往右第$w$列的格子用$(h,w)$表示。在$(h,w)$这个格子上写着一个非负整数$A_{h,w}$。

高桥君一开始位于格子$(sh,sw)$，接下来他将对网格进行$Q$次修改。第$i$次修改由一个字符$d_i（d_i$是$L、R、U、D$中的一个$）$和一个非负整数$a_i$给出，这意味着高桥君将执行以下操作：

按照$d_i$的方向移动$1$个格子。也就是说，如果$d_i$是$L$，就向左移动；如果$d_i$是$R$，就向右移动；如果$d_i$是$U$，就向上移动；如果$d_i$是$D$，就向下移动。然后，将移动到的格子设为$(h,w)$，并将$A_{h,w}$改为$a_i$。

保证在每次修改中，高桥君都可以按照d_i的方向移动1个格子。

每次修改网格后，请输出以下问题的答案：

• 如果一个格子序列$P=((h_1,w_1),…,(h_M,w_M))$满足以下所有条件，那么称$P$为一条路径：
• $(h_1,w_1)=(1,1)，(h_M,w_M)=(H,W)，M=H+W-1$。
• 对于任意满足1≤i≤M-1的i，都有(h_{i+1},w_{i+1})=(h_i+1,w_i)或者(h_{i+1},w_{i+1})=(h_i,w_i+1)。
• 从(1,1)到(H,W)的路径有$\frac{H+W−2}{H−1}$条。
• 对于路径$P=((h_1,w_1),…,(h_M,w_M))$，定义$f(P)=∏_{1≤i≤M}\times A_{h_i,w_i}$。求所有路径$P$的$f(P)$之和对$998244353$取余的结果。

【输入格式】

$H W\\ A_{1,1}\hspace{0.2cm}A_{1,2}\hspace{0.2cm}...\hspace{0.2cm}A_{1,W}\\ ⋮\\ A_{H,1}\hspace{0.2cm}A_{H,2}\hspace{0.2cm}...\hspace{0.2cm}A_{H,W}\\ Q\hspace{0.2cm}sh\hspace{0.2cm}sw\\ d_1\hspace{0.2cm}a_1\\ ⋮\\ d_Q\hspace{0.2cm}a_Q\\$

第一行输入$H$和$W$。
接下来$H$行，每行$W$个数，代表$A_{1,1}$至$A_{H,W}$。
然后输入三个数$Q,sh,sw$。
最后输入$Q$行，每行$1$个字符和$1$个整数，表示$d_i,a_i$。

【输出格式】

输出$Q$行。 第$i$行输出第$i$次修改网格后，所有路径$P$对应的$f(P)$之和。（答案对$998244353$取余）

【样例组】

输入1

2 3
1 2 3
4 5 6
3 2 2
U 7
R 8
L 9

输出1

456
666
822

输入2

5 4
147015809 294958521 852121867 499798308
790350368 404692331 645419803 290531806
275766153 896286651 239187926 945049742
340760022 236352314 926236110 223464913
287023679 590772036 340282357 521075891
6 3 1
U 344644511
R 45812235
D 260083498
R 781118585
L 156297846
L 411901560

输出2

299123226
548055393
810247224
876210800
773990840
506814544

【样例解释】

【样例解释#1】

最初，高桥君位于$(2,2)$。

• 向上移动，将$A_{1,2}$改为$7$。各路径对应的$f(P)$如下：
  • $P=((1,1),(1,2),(1,3),(2,3))：f(P)=1×7×3×6=126$。
  • $P=((1,1),(1,2),(2,2),(2,3))：f(P)=1×7×5×6=210$。
  • $P=((1,1),(2,1),(2,2),(2,3))：f(P)=1×4×5×6=120$。
• 向右移动，将$A_{1,3}$改为$8$。各路径对应的$f(P)$如下：
  • $P=((1,1),(1,2),(1,3),(2,3))：f(P)=1×7×8×6=336$。
  • $P=((1,1),(1,2),(2,2),(2,3))：f(P)=1×7×5×6=210$。
  • $P=((1,1),(2,1),(2,2),(2,3))：f(P)=1×4×5×6=120$。
• 向左移动，将$A_{1,2}$改为$9$。各路径对应的$f(P)$如下：
  • $P=((1,1),(1,2),(1,3),(2,3))：f(P)=1×9×8×6=432$。
  • $P=((1,1),(1,2),(2,2),(2,3))：f(P)=1×9×5×6=270$。
  • $P=((1,1),(2,1),(2,2),(2,3))：f(P)=1×4×5×6=120$。

【数据范围】

$2 ≤ H, W ≤ 200000\\ H\times W ≤ 200000\\ 0 ≤ A_{h,w} < 998244353\\ 1 ≤ Q ≤ 200000\\ 1 ≤ sh ≤ H, 1 ≤ sw ≤ W\\ 0 ≤ a_i < 998244353\\ H, W, A_{h,w}, Q, sh, sw, a_i$均为整数。
$d_i$是L、R、U、D中的一个 在每次修改中，高桥君都可以向$d_i$方向移动$1$个格子