{"raw_statement":[{"iden":"statement","content":"In \"_The Man in the High Castle_\" world, there are $m$ different film endings.\n\nAbendsen owns a storage and a shelf. At first, he has $n$ ordered films on the shelf. In the $i$\\-th month he will do:\n\n1.  Empty the storage.\n2.  Put $k_i \\cdot m$ films into the storage, $k_i$ films for each ending.\n3.  He will think about a question: if he puts all the films from the shelf into the storage, then randomly picks $n$ films (from all the films in the storage) and rearranges them on the shelf, what is the probability that sequence of endings in $[l_i, r_i]$ on the shelf will not be changed? Notice, he just thinks about this question, so the shelf will not actually be changed.\n\nAnswer all Abendsen's questions.\n\nLet the probability be fraction $P_i$. Let's say that the total number of ways to take $n$ films from the storage for $i$\\-th month is $A_i$, so $P_i \\cdot A_i$ is always an integer. Print for each month $P_i \\cdot A_i \\pmod {998244353}$.\n\n$998244353$ is a prime number and it is equal to $119 \\cdot 2^{23} + 1$.\n\nIt is guaranteed that there will be only no more than $100$ different $k$ values."},{"iden":"input","content":"The first line contains three integers $n$, $m$, and $q$ ($1 \\le n, m, q \\le 10^5$, $n+q\\leq 10^5$) — the number of films on the shelf initially, the number of endings, and the number of months.\n\nThe second line contains $n$ integers $e_1, e_2, \\ldots, e_n$ ($1\\leq e_i\\leq m$) — the ending of the $i$\\-th film on the shelf.\n\nEach of the next $q$ lines contains three integers $l_i$, $r_i$, and $k_i$ ($1 \\le l_i \\le r_i \\le n, 0 \\le k_i \\le 10^5$) — the $i$\\-th query.\n\nIt is guaranteed that there will be only no more than $100$ different $k$ values."},{"iden":"output","content":"Print the answer for each question in a separate line."},{"iden":"examples","content":"Input\n\n6 4 4\n1 2 3 4 4 4\n1 4 0\n1 3 2\n1 4 2\n1 5 2\n\nOutput\n\n6\n26730\n12150\n4860\n\nInput\n\n5 5 3\n1 2 3 4 5\n1 2 100000\n1 4 4\n3 5 5\n\nOutput\n\n494942218\n13125\n151632"},{"iden":"note","content":"In the first sample in the second query, after adding $2 \\cdot m$ films into the storage, the storage will look like this: ${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$.\n\nThere are $26730$ total ways of choosing the films so that $e_l, e_{l+1}, \\ldots, e_r$ will not be changed, for example, $[1, 2, 3, 2, 2]$ and $[1, 2, 3, 4, 3]$ are such ways.\n\nThere are $2162160$ total ways of choosing the films, so you're asked to print $(\\frac{26730}{2162160} \\cdot 2162160) \\mod 998244353 = 26730$."}],"translated_statement":[{"iden":"statement","content":"在《高堡奇人》的世界中，有 $m$ 种不同的电影结局。\n\nAbendsen 拥有一个存储空间和一个书架。最初，他书架上有 $n$ 部有序的电影。在第 $i$ 个月，他会执行：\n\n回答 Abendsen 的所有问题。\n\n设概率为分数 $P_i$。设第 $i$ 个月从存储中选取 $n$ 部电影的总方式数为 $A_i$，则 $P_i dot.op A_i$ 总是整数。请对每个月输出 $P_i dot.op A_i pmod 998244353$。\n\n$998244353$ 是一个质数，等于 $119 dot.op 2^(23) + 1$。\n\n保证不同的 $k$ 值不超过 $100$ 个。\n\n第一行包含三个整数 $n$，$m$ 和 $q$（$1 lt.eq n, m, q lt.eq 10^5$，$n + q lt.eq 10^5$）——初始书架上的电影数量、结局数量和月份数。\n\n第二行包含 $n$ 个整数 $e_1, e_2, dots.h, e_n$（$1 lt.eq e_i lt.eq m$）——书架上第 $i$ 部电影的结局。\n\n接下来的 $q$ 行每行包含三个整数 $l_i$，$r_i$ 和 $k_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$0 lt.eq k_i lt.eq 10^5$）——第 $i$ 个查询。\n\n保证不同的 $k$ 值不超过 $100$ 个。\n\n请对每个查询的答案单独输出一行。\n\n在第一个样例的第二个查询中，向存储中添加 $2 dot.op m$ 部电影后，存储将变为：${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$。\n\n共有 $26730$ 种选择电影的方式，使得 $e_l, e_(l + 1), dots.h, e_r$ 保持不变，例如 $[ 1, 2, 3, 2, 2 ]$ 和 $[ 1, 2, 3, 4, 3 ]$ 就是这样的方式。\n\n共有 $2162160$ 种选择电影的总方式，因此你需要输出 $(frac(26730, 2162160) dot.op 2162160) mod 998244353 = 26730$。"},{"iden":"input","content":"第一行包含三个整数 $n$，$m$ 和 $q$（$1 lt.eq n, m, q lt.eq 10^5$，$n + q lt.eq 10^5$）——初始书架上的电影数量、结局数量和月份数。第二行包含 $n$ 个整数 $e_1, e_2, dots.h, e_n$（$1 lt.eq e_i lt.eq m$）——书架上第 $i$ 部电影的结局。接下来的 $q$ 行每行包含三个整数 $l_i$，$r_i$ 和 $k_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$0 lt.eq k_i lt.eq 10^5$）——第 $i$ 个查询。保证不同的 $k$ 值不超过 $100$ 个。"},{"iden":"output","content":"请对每个查询的答案单独输出一行。"},{"iden":"examples","content":"输入6 4 41 2 3 4 4 41 4 01 3 21 4 21 5 2输出626730121504860输入5 5 31 2 3 4 51 2 1000001 4 43 5 5输出49494221813125151632"},{"iden":"note","content":"在第一个样例的第二个查询中，向存储中添加 $2 dot.op m$ 部电影后，存储将变为：${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$。共有 $26730$ 种选择电影的方式，使得 $e_l, e_(l + 1), dots.h, e_r$ 保持不变，例如 $[ 1, 2, 3, 2, 2 ]$ 和 $[ 1, 2, 3, 4, 3 ]$ 就是这样的方式。共有 $2162160$ 种选择电影的总方式，因此你需要输出 $(frac(26730, 2162160) dot.op 2162160) mod 998244353 = 26730$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 1 \\le n, m, q \\le 10^5 $ and $ n + q \\le 10^5 $.  \nLet $ E = (e_1, e_2, \\dots, e_n) $ be the initial sequence of film endings, where $ e_i \\in \\{1, 2, \\dots, m\\} $.  \nFor each query $ i \\in \\{1, \\dots, q\\} $, let $ (l_i, r_i, k_i) $ denote:  \n- $ l_i, r_i \\in \\mathbb{Z} $: indices defining a contiguous subsequence $ E[l_i:r_i] $ to remain unchanged.  \n- $ k_i \\in \\mathbb{Z}_{\\ge 0} $: number of **additional** films of **each** ending added to storage (i.e., storage gains $ k_i $ copies of each of the $ m $ endings).  \n\nLet $ S_i $ be the set of all possible sequences of $ n $ films chosen from storage (after adding $ k_i $ copies per ending) such that the subsequence from index $ l_i $ to $ r_i $ matches $ E[l_i:r_i] $.  \n\nLet $ A_i $ be the total number of ways to choose any sequence of $ n $ films from storage (after adding $ k_i $ copies per ending).  \nLet $ P_i = \\frac{|S_i|}{A_i} $ be the probability that a random sequence matches $ E[l_i:r_i] $ on positions $ l_i $ to $ r_i $.  \n\n**Constraints**  \n1. $ 1 \\le l_i < r_i \\le n $  \n2. $ 0 \\le k_i \\le 10^5 $  \n3. There are at most 100 distinct values of $ k_i $ across all queries.  \n4. Storage initially contains no films; after query $ i $, storage has $ k_i $ copies of each of the $ m $ endings (i.e., total $ m \\cdot k_i $ films added).  \n5. The shelf must be filled with exactly $ n $ films, each chosen from storage (with unlimited supply per ending after addition).  \n6. The subsequence $ E[l_i:r_i] $ must be preserved exactly in positions $ l_i $ to $ r_i $.  \n\n**Objective**  \nFor each query $ i $, compute:  \n$$\nP_i \\cdot A_i \\mod 998244353 = |S_i| \\mod 998244353\n$$  \nThat is, output the number of valid sequences $ \\in S_i $ modulo $ 998244353 $.","simple_statement":null,"has_page_source":false}