{"raw_statement":[{"iden":"statement","content":"Are you tired of city life? Have you ever had illusions of pastoral peace? The clean atmosphere, the closeness to nature and the gentle pace of living, all made Setsuna yearn for the pastoral life more.\n\nIn order to experience the simple pastoral life, Setsuna has moved to Star Valley and started her farming journey.\n\nSoon, she discovers the problem: overgrown weeds are harming her farm. In Chinese, we call it \"Sheng Cao\". She realized that weeding should be put at the top priority.\n\nThe farm can be described as an $n times m$ matrix. The growth rate of weed in row $i$ and column $j$ is denoted as $a_{i , j}$, indicating that the weed will grow $a_{i , j}$ units every *beginning* of the moment. At the end of moment $0$, there is no weed on the farm. \n\nSetsuna will use mower $k$ times, where the $i$-th use occurs at the *end* of moment $t_i$. Each use of the mower completely removes weeds in a row or column. \n\nSetsuna wonders how many units of weed she will remove.\n\nThe answer might be very large, so please output the desired answer modulo $998244353$.\n\nThe first line contains three integers $n, m, k (1 <= n, m <= 500, 1 <= k <= 3 times 10^5)$.\n\nThe next $n$ lines contains $m$ integers each, where the $j$-th integer of the $i$-th line is $a_{i , j} (0 <= a_{i , j} <= 10^(18))$.\n\nThe $i$-th of the next $k$ lines contains one character and two integers.\n\nIt is guaranteed that $1 <= x_i <= n, 1 <= y_i <= m, 1 <= t_i <= 10^(18)$ hold for $1 <= i <= k$ and $t_i$ is strictly increasing.\n\nOutput one integer indicating the answer modulo $998244353$.\n\nSample $1$:\n\nAt the end of moment $0$, the farm looks like\n\n$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 0 & 0 \\\\ \\end{matrix} \\right] $$\n\nAt the end of moment $5$, Setsuna has cleared row $1$ and $15$ units of weed has been cut, so the farm looks like\n\n$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 15 & 20 \\\\ \\end{matrix} \\right] $$\n\nAt the end of moment $6$, Setsuna has cleared column $2$ and $26$ units of weed has been cut, so the farm looks like\n\n$$ \\left[ \\begin{matrix} 1 & 0 \\\\ 18 & 0 \\\\ \\end{matrix} \\right] $$\n\nAt the end of moment $7$, Setsuna has cleared row $1$ and $4$ units of weed has been cut, so the farm looks like\n\n$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 21 & 4 \\\\ \\end{matrix} \\right] $$\n\nSo the answer is $15 + 26 + 4 = 45$ units.\n\n"},{"iden":"input","content":"The first line contains three integers $n, m, k (1 <= n, m <= 500, 1 <= k <= 3 times 10^5)$.The next $n$ lines contains $m$ integers each, where the $j$-th integer of the $i$-th line is $a_{i , j} (0 <= a_{i , j} <= 10^(18))$.The $i$-th of the next $k$ lines contains one character and two integers.  $\"r\"\" \"x_i \" \"t_i$ - Setsuna clears the weeds in row $x_i$ at the end of moment $t_i$.  $\"c\"\" \"y_i \" \"t_i$ - Setsuna clears the weeds in column $y_i$ at the end of moment $t_i$. It is guaranteed that $1 <= x_i <= n, 1 <= y_i <= m, 1 <= t_i <= 10^(18)$ hold for $1 <= i <= k$ and $t_i$ is strictly increasing."},{"iden":"output","content":"Output one integer indicating the answer modulo $998244353$."},{"iden":"examples","content":"Input2 2 3\n1 2\n3 4\nr 1 5\nc 2 6\nr 1 7\nOutput45\nInput3 4 1\n1 2 3 4\n5 6 7 8\n9 10 11 12\nr 1 1000000000000000000\nOutput172998509\n"},{"iden":"note","content":"Sample $1$:At the end of moment $0$, the farm looks like$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 0 & 0 \\\\ \\end{matrix} \\right] $$At the end of moment $5$, Setsuna has cleared row $1$ and $15$ units of weed has been cut, so the farm looks like$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 15 & 20 \\\\ \\end{matrix} \\right] $$At the end of moment $6$, Setsuna has cleared column $2$ and $26$ units of weed has been cut, so the farm looks like$$ \\left[ \\begin{matrix} 1 & 0 \\\\ 18 & 0 \\\\ \\end{matrix} \\right] $$At the end of moment $7$, Setsuna has cleared row $1$ and $4$ units of weed has been cut, so the farm looks like$$ \\left[ \\begin{matrix} 0 & 0 \\\\ 21 & 4 \\\\ \\end{matrix} \\right] $$So the answer is $15 + 26 + 4 = 45$ units."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the dimensions of the farm and the number of mowing operations.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}^{n \\times m} $ be the growth rate matrix, where $ a_{i,j} $ is the growth rate of weeds at cell $ (i,j) $.  \nLet $ T = (t_1, t_2, \\dots, t_k) $ be a strictly increasing sequence of mowing times, with $ t_i \\in \\mathbb{Z}^+ $ and $ t_1 \\geq 1 $.  \nLet $ O = (o_1, o_2, \\dots, o_k) $ be the sequence of operations, where each $ o_i \\in \\{ \\text{row}, \\text{col} \\} \\times \\{1,\\dots,n\\} \\times \\{1,\\dots,m\\} $, specifying the type (row/column), index, and time $ t_i $ of the $ i $-th mowing.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 500 $  \n2. $ 1 \\leq k \\leq 3 \\times 10^5 $  \n3. $ 0 \\leq a_{i,j} \\leq 10^{18} $ for all $ i \\in \\{1,\\dots,n\\}, j \\in \\{1,\\dots,m\\} $  \n4. $ 1 \\leq t_1 < t_2 < \\dots < t_k \\leq 10^{18} $\n\n**Objective**  \nCompute the total weed mass removed over all $ k $ mowing operations, modulo $ 998244353 $.\n\nLet $ R_i $ denote the total weed mass removed at the $ i $-th mowing.  \nIf $ o_i $ is a row operation on row $ r $, then:  \n$$\nR_i = \\sum_{j=1}^m \\left( a_{r,j} \\cdot \\left( t_i - t_{\\text{last\\_clear\\_row}(r)} \\right) \\cdot \\prod_{\\substack{\\ell < i \\\\ o_\\ell \\text{ is col} \\\\ \\text{and col index } c}} \\mathbf{1}_{c \\text{ not cleared after last row } r \\text{ clear}} \\right)\n$$  \nBut more cleanly, define:  \n\nLet $ \\text{last\\_row}[r] $ be the last time row $ r $ was mowed before $ t_i $, or $ 0 $ if never.  \nLet $ \\text{last\\_col}[c] $ be the last time column $ c $ was mowed before $ t_i $, or $ 0 $ if never.  \n\nThen, the effective growth time for cell $ (i,j) $ before the $ i $-th mowing is:  \n$$\n\\tau_{i,j} = t_i - \\max\\left( \\text{last\\_row}[i], \\text{last\\_col}[j] \\right)\n$$  \nBut since mowing clears entire row or column, and weeds grow continuously, the correct model is:  \n\nAt any moment, the weed at $ (i,j) $ grows at rate $ a_{i,j} $.  \nWhen a row $ r $ is mowed at time $ t $, the weed removed from cell $ (r,j) $ is:  \n$$\na_{r,j} \\cdot \\left( t - \\text{last\\_clear}(r,j) \\right)\n$$  \nwhere $ \\text{last\\_clear}(r,j) = \\max( \\text{last\\_row\\_clear}[r], \\text{last\\_col\\_clear}[j] ) $\n\nThus, define:  \n- Let $ r_{\\text{last}}[i] $ be the last time row $ i $ was mowed (initially 0).  \n- Let $ c_{\\text{last}}[j] $ be the last time column $ j $ was mowed (initially 0).  \n\nFor each operation $ i $ at time $ t_i $:  \n- If it mows row $ r $:  \n  $$\n  R_i = \\sum_{j=1}^m a_{r,j} \\cdot \\left( t_i - \\max(r_{\\text{last}}[r], c_{\\text{last}}[j]) \\right)\n  $$  \n  Then update $ r_{\\text{last}}[r] = t_i $  \n- If it mows column $ c $:  \n  $$\n  R_i = \\sum_{i=1}^n a_{i,c} \\cdot \\left( t_i - \\max(r_{\\text{last}}[i], c_{\\text{last}}[c]) \\right)\n  $$  \n  Then update $ c_{\\text{last}}[c] = t_i $\n\n**Total Answer:**  \n$$\n\\boxed{ \\sum_{i=1}^k R_i \\mod 998244353 }\n$$","simple_statement":"You are given a tree with n nodes rooted at 1. Each node has a beauty value. For each query, you are given a list of nodes: s₁, s₂, ..., sₖ. You must find the maximum beauty in the subtree of s₁, but exclude all nodes that are in the subtrees of s₂, s₃, ..., sₖ. If s₁ is inside any of the subtrees of s₂ to sₖ, or if no nodes remain after exclusion, output -1.","has_page_source":false}