Interval Queries

题号：NC222407
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given a sequence $A_{}$ of length $n_{}$ and $q_{}$ quries. For each query, three integers $l,r,k_{}$ are given and you should calculate:
$\sum_{i=0}^{k-1} f(\{A_{l-i}, ..., A_l, A_{l+1}, ..., A_r, ..., A_{r+i}\}) \times (n+1)^i \pmod{998244353}$
where $f(S) = \max\{len \; | \; \exists x, \forall u \in \{x, x+1, \cdots, x+len-1\}, u\in S\}$ .

输入描述:

The first line contains two integers , denoting the length of given sequence and the number of quries respectively.

The second line contains  integers , denoting the given sequence.

Following  lines each contains three integers , denoting each query.

It's guaranteed that .

输出描述:

Output  lines each containing one integer, denoting the answers to the queries.

示例1

输入

复制

输出

复制

19
193

说明

For the first query, , so the answer is .

For the second query, , so the answer is .