给定固定的整数 $k$ 和 $w$。 对于一个长度为 $n$ 的数组 $a$，我们按如下方式定义其权值：

• 令 $b$ 为数组 $a$ 按非降序排序后的数组。
• 数组 $a$ 的权值定义为 $\sum_{i=1}^{n} \lfloor \frac{b_i \cdot i^k}{w} \rfloor$。

此处，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。 例如，若 $k = 3$ 且 $w = 3$，则数组 $a = [3, 2, 2]$ 的权值为： $\lfloor \frac{2 \cdot 1^3}{3} \rfloor + \lfloor \frac{2 \cdot 2^3}{3} \rfloor + \lfloor \frac{3 \cdot 3^3}{3} \rfloor = 0 + 2 + 9 = 11$。

给定一个初始数组 $a$ 以及 $q$ 次查询。每次查询会修改数组 $a$ 中的一个元素。 在每次修改后，你需要输出数组的新权值。由于数组权值可能非常大，请输出其对 $998\,244\,353$ 取模的结果。 注意，修改在查询之间是持久的。例如，第二次查询是在第一次查询修改后的数组基础上进行的。

输入格式

第一行包含三个整数 $n, k, w$ ($1 \le n \le 10^5, 1 \le k \le 5, 1 \le w \le 5$)：数组的长度以及题目中给定的参数。 第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^5$)：原始数组的元素。 第三行包含一个整数 $q$ ($1 \le q \le 10^5$)：查询次数。 接下来的 $q$ 行，每行包含两个整数 $pos$ 和 $x$ ($1 \le pos \le n, 0 \le x \le 10^5$)。这表示将 $a_{pos}$ 修改为 $x$ 的查询。

输出格式

输出 $q$ 个整数：每次修改后数组的权值，对 $998\,244\,353$ 取模。

样例

样例输入 1

3 1 1
2 2 8
2
2 5
3 6

样例输出 1

36
30

样例输入 2

4 2 2
1 3 3 7
4
1 1
2 4
3 8
4 8

样例输出 2

75
80
103
108