Problem Statement

There is an $H \times W$ grid. Let $(h,w)$ denote the cell at the $h$-th row from the top and the $w$-th column from the left. A non-negative integer $A_{h,w}$ is written in cell $(h,w)$.

Takahashi starts at cell $(sh,sw)$ and will perform $Q$ changes to the grid. The $i$-th change is given by a character $d_i$ ($d_i$ is one of L, R, U, D) and a non-negative integer $a_i$, meaning Takahashi will do the following:

• Move one cell in the direction $d_i$. That is, if $d_i$ is L, move left; if R, move right; if U, move up; if D, move down by one cell. Then, let the destination cell be $(h,w)$, and set $A_{h,w}$ to $a_i$.

It is guaranteed that in each change, he can move one cell in direction $d_i$.

After each change, print the answer to the following problem:

A sequence of cells $P = ((h_1,w_1), \ldots, (h_{M},w_{M}))$ is said to be a path if and only if it satisfies all of the following conditions:

• $(h_1,w_1) = (1,1)$, $(h_{M},w_{M}) = (H,W)$, and $M = H + W - 1$.
• For every $i$ with $1 \leq i \leq M-1$, either $(h_{i+1}, w_{i+1}) = (h_i + 1, w_i)$ or $(h_{i+1}, w_{i+1}) = (h_i, w_i + 1)$.

There are $\binom{H+W-2}{H-1}$ paths. For a path $P = ((h_1,w_1), \ldots, (h_{M},w_{M}))$, define $f(P) = \prod_{1\leq i\leq M}A_{h_i,w_i}$. Print the sum, modulo $998244353$, of $f(P)$ over all paths $P$.

Constraints

• $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$, and $a_i$ are integers.
• Each $d_i$ is L, R, U, or D.
• In each change, Takahashi can move one cell in the direction $d_i$.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines.

The $i$-th line should contain the sum, modulo $998244353$, of $f(P)$ over all paths $P$ after performing the $i$-th change to the grid.