题目描述

有 $n$ 个顾客，每位顾客会点一道菜。做第 $i$ 道菜需要花费 $a_i$ 的时间，这位顾客吃完这道菜需要花费 $b_i$ 的时间。

你只能在同一个时刻做一道菜。对于每位顾客，一旦上菜，即对应的菜做完，他便开始吃，吃完之后就会离开。

给定一个整数 $k$，你想选择服务其中的 $k$ 位顾客，并且可以按任意顺序服务，使得你的劳动时间最短。这里的“劳动时间”指从做第一道菜开始，到最后一位顾客吃完离开的时间。

现在给定 $b_1,b_2,\ldots,b_n$ 和 $k$。对于所有每个数都在 $1$ 到 $V$ 之间的数列

$$a_1,a_2,\ldots,a_n$$

一共有 $V^n$ 个，求出最短劳动时间的总和。输出答案对 $998244353$ 取模的结果。

你需要回答 $q$ 组询问。每组询问的 $b$ 数组和 $V$ 都相同，只有 $k$ 可能不同。

输入格式

第一行三个整数 $n,V,q$。

接下来一行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

接下来一行 $q$ 个整数，表示各个询问的 $k$。

输出格式

一共 $q$ 行，每行一个整数，表示答案。

样例 1 输入

2 2 2
1 2
1 2

样例 1 输出

10
16

样例 1 解释

当 $k=1$ 时，$A=(1,1),(1,2),(2,1),(2,2)$ 的答案分别是 $2,2,3,3$。

当 $k=2$ 时，$A=(1,1),(1,2),(2,1),(2,2)$ 的答案分别是 $3,4,4,5$。

样例 2 输入

3 5 3
1 2 4
1 2 3

样例 2 输出

448
787
1255

样例 3 输入

10 10 10
14 38 45 9 19 18 7 18 33 21
1 2 3 4 5 6 7 8 9 10

样例 3 输出

663655052
615617049
323725023
554911324
803518888
499232802
916051842
54293837
639852351
260050903

数据范围

对于所有数据，保证：

$$1\le n\le 30, \qquad 1\le V\le 20, \qquad 1\le b_i\le 600, \qquad 1\le q,k\le n.$$

子任务	$n$	$V$	特殊性质	分数
1	$\le 5$	$\le 3$	无	10
2	$\le 9$			20
3	$\le 30$	$\le 20$	A	10
4			B
5		$\le 3$	无	20
6		$\le 20$		30

特殊性质：

• A：保证 $1\le k\le 2$。
• B：保证 $n-1\le k\le n$。