分数: 800 点
问题陈述
有一个 H \times W 网格。让 (h,w) 表示位于 h从顶部算起的第行和 w左起第 列。非负整数 A_{h,w} 写入单元格 (h,w).
高桥从牢房开始 (sh,sw) 并将执行 Q 更改为网格。的 i-th 更改由字符给出 d_i (d_i 是其中之一 L, R, U, D) 和一个非负整数 a_i,意味着高桥将执行以下操作:
- 朝 方向移动一个单元格 d_i。也就是说,如果 d_i is
L,向左移动;如果R,向右移动;如果U,向上移动;如果D,向下移动一个单元格。然后,让目标单元格为 (h,w),并设置 A_{h,w} to a_i.
保证在每次改变时,他可以向方向移动一个单元格 d_i.
每次更改后,打印以下问题的答案:
一系列细胞 P = ((h_1,w_1), \ldots, (h_{M},w_{M})) 据说是 路径 当且仅当满足以下所有条件时:
- (h_1,w_1) = (1,1), (h_{M},w_{M}) = (H,W),和 M = H + W - 1.
- 对于每个 i 与 1 \leq i \leq M-1,或者 (h_{i+1}, w_{i+1}) = (h_i + 1, w_i) or (h_{i+1}, w_{i+1}) = (h_i, w_i + 1).
有 \binom{H+W-2}{H-1} 路径。对于一条路径 P = ((h_1,w_1), \ldots, (h_{M},w_{M})),定义 f(P) = \prod_{1\leq i\leq M}A_{h_i,w_i}。打印总和,模数 998244353,属于 f(P) 在所有路径上 P.
约束
- 2 \leq H, W \leq 200000
- HW \leq 200000
- 0 \leq A_{h,w} < 998244353
- 1 \leq Q \leq 200000
- 1 \leq sh \leq H, 1 \leq sw \leq W
- 0 \leq a_i < 998244353
- H, W, A_{h,w}, Q, sh, sw,和 a_i 是整数。
- 每个 d_i is
L,R,U,或D. - 在每次变化中,高桥可以朝以下方向移动一个单元格 d_i.
输入
输入由标准输入按以下格式给出:
H W
A_{1,1} \cdots A_{1,W}
\vdots
A_{H,1} \cdots A_{H,W}
Q sh sw
d_1 a_1
\vdots
d_Q a_Q
输出
打印 Q 行。
的 i- 第行应包含求和、模数 998244353,属于 f(P) 在所有路径上 P 执行后 i- 对网格的更改。
示例输入 1
2 3 1 2 3 4 5 6 3 2 2 U 7 R 8 L 9
示例输出 1
456 666 822
- 最初,高桥位于 (2,2).
- 向上移动,然后设置 A_{1,2} to 7。的价值
每个路径的 f(P) 是:
- P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 7 \times 3 \times 6=126.
- P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 7 \times 5 \times 6=210.
- P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.
- 向右移动,然后设置 A_{1,3} to 8。的价值
每个路径的 f(P) 是:
- P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 7 \times 8 \times 6=336.
- P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 7 \times 5 \times 6=210.
- P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.
- 向左移动,然后设置 A_{1,2} to 9。的价值
每个路径的 f(P) 是:
- P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 9 \times 8 \times 6=432.
- P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 9 \times 5 \times 6=270.
- P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.
示例输入 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