問題文

ぴなさんは $\displaystyle\sum_{1\leq i<j\leq n}ij=\frac{1}{2}\left(\left(\sum_{k=1}^{n}k\right)^2 - \left(\sum_{k=1}^{n}k^2\right)\right)$ という公式が好きです。

ところで、正整数 $N$ と長さ $N$ の整数列 $\{P_n\}$ が与えられます。
以下の $Q$ 個のクエリへ回答してください。
・$1 \leq A < B \leq N$ を満たす $2$ つの整数 $A, B$ と $1 \leq K \leq B-A+1$ を満たす整数 $K$ が与えられるので、$P_A, P_{A+1}, \dots, P_B$ から $K$ 個選ぶ全ての場合に対して $K$ 個の項の積を計算し、それらの総和を出力してください。

入力

$N$
$P_1\ \ P_2\ \ \cdots\ P_N$
$Q$
$A_1\ \ B_1\ \ K_1$
$A_2\ \ B_2\ \ K_2$
$\vdots$
$A_Q\ \ B_Q\ \ K_Q$

・$2\leq N\leq 5000$
・$-10^9\leq P_i\leq 10^9\ (1\leq i\leq N)$
・$1\leq Q\leq 5000$
・$1\leq A_i < B_i\leq N (1\leq i\leq Q)$
・$1\leq K_i\leq B_i-A_i+1 (1\leq i\leq Q)$
・入力はすべて整数

出力

各クエリの答えを一行毎に出力し、最後に改行してください。
ただし、答えは非常に大きくなる可能性があるので、答えを $998244353$ で割った余り( $0$ 以上 $998244353$ 未満の整数 )を出力してください。

サンプル

5
1 2 3 4 5
3
1 5 1
2 4 2
3 5 3

15
26
60