由于原题 1 秒的时限相对于本题复杂度上限极其不合理，本评测时限改为 5 秒，同时数据范围进行了一些微调。但是我们的 std 之一可以保证在 1 秒内同时通过官方数据和民间数据。

时间限制： 1.0 秒 5.0 秒

空间限制： 256 MB

题目描述

给出取模意义下的线性递推式：

$$ a_n \equiv \sum_{i=1}^{\min(n,m)}{k_ia_{n-i} } \pmod Q $$

上式对 $n \in \mathbb{N}^+$ 成立，有 $a_0=1$，并且满足 $0\le a_n < Q$。其中 $m,k_1,k_2,\dots,k_m,Q$ 为给定的非负整数，$m,Q > 0$，$a \equiv b \pmod Q$ 表示 $a$ 和 $b$ 除以 $Q$ 的余数相等。

已知 $Q=998244353$。给出非负整数 $l,r\ (l\le r)$，求 $a_l, a_{l+1}, \dots, a_r$ 对 $Q$ 取模的结果。

输入格式

从标准输入读入数据。

输入的第一行包含 $3$ 个非负整数 $m,l,r$。其中 $l \le r$。

第二行包含 $m$ 个非负整数 $k_1,k_2,\dots,k_m$，保证 $0 \le k_1,k_2,\dots,k_m < Q$。

输出格式

输出到标准输出。

输出 $r-l+1$ 行，每行一个正整数，分别表示 $a_l, a_{l+1},\dots,a_r$ 对 $Q$ 取模的结果。

3 3 6
2 0 4

12
32
80
208

样例 1 解释

$k_1 = 2,k_2=0,k_3=4$。需要求出 $a_3,a_4,a_5,a_6$。

$a_1 = k_1 a_0 = 2 \times 1 = 2$；

$a_2 = k_1 a_1 + k_2 a_0 = 2 \times 2 + 0 \times 1 = 4$；

$a_3 = k_1 a_2 + k_2 a_1 + k_3 a_0 = 2 \times 4 + 0 \times 2 + 4 \times 1 = 12$；

$a_4 = k_1 a_3 + k_2 a_2 + k_3 a_1 = 2 \times 12 + 0 \times 4 + 4 \times 2 = 32$；

$a_5 = k_1 a_4 + k_2 a_3 + k_3 a_2 = 2 \times 32 + 0 \times 12 + 4 \times 4 = 80$；

$a_6 = k_1 a_5 + k_2 a_4 + k_3 a_3 = 2 \times 80 + 0 \times 32 + 4 \times 12 = 208$；

2 1 11
1 1

1
2
3
5
8
13
21
34
55
89
144

样例 2 解释

因为 $k_1=k_2=1$，因此这组样例就是斐波那契数列 $a_n = a_{n-1} + a_{n-2}$。

10 10 20
532737790 634932889 335818534 101179174 977780682 695192541 779962395 295668292 157661238 325351676

119744921
651421717
601080475
163399777
291546699
108479226
406175654
344671679
459752012
489415425
349454810

子任务

对于所有数据，保证 $1\le m\le 10^5,1\le l\le 10^{12},0\le r-l\le 3\times 10^5$。

子任务 1（97 分）：传统计分，每组测试点满足以下限制：

测试点编号	$m=r-l=$	$l=$
$1$	$10$
$2$	$10^3$
$3\sim 4$	$10^5$
$5\sim 6$	$10^2$	$10^{12}$
$7\sim 8$	$10^3$
$9\sim 10$	$10^5$

子任务 2（3 分）：捆绑测试，无特殊限制。