AT_arc190_c [ARC190C] Basic Grid Problem with Updates

$ H\times 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` ならば下方向に $ 1 $ マス移動する．その後，移動先のマスを $ (h,w) $ とするとき $ A_{h,w} $ を $ a_i $ に変更する． ただし，各変更において，高橋君が $ d_i $ 方向に $ 1 $ マス移動することが可能であることが保証されます． マス目の変更のたびに，以下の問題の答を出力してください． > マスの列 $ P=((h_1,w_1),\ldots,(h_{M},w_{M})) $ が以下の条件をすべて満たすとき， $ P $ は**パス**であるということにします． > > - $ (h_1,w_1)=(1,1) $ , $ (h_{M},w_{M})=(H,W) $ , $ M=H+W-1 $ . > - $ 1\leq i \leq 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) $ が成り立つ． > > パスは $ \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} $ と定めます． すべてのパス $ P $ に対する $ f(P) $ の総和を $ 998244353 $ で割った余りを出力してください．

入力は以下の形式で標準入力から与えられます． > $ 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 $ 行目には $ i $ 回目のマス目の変更の後に，すべてのパス $ P $ に対する $ f(P) $ の総和を $ 998244353 $ で割った余りを出力してください．

### Sample Explanation 1 - はじめ高橋君は $ (2,2) $ に居ます． - 上方向に移動して， $ A_{1,2} $ を $ 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} $ を $ 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} $ を $ 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 $ . ### 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, a_i $ は整数 - $ d_i $ は `L`, `R`, `U`, `D` のいずれか - 各変更において，高橋君が $ d_i $ 方向に $ 1 $ マス移動することが可能である