B. Bruteforce
time limit per test
5 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given fixed integers $$$k$$$ and $$$w$$$.

For an array $$$a$$$ of length $$$n$$$, let us define its weight in the following way:

  • Let $$$b$$$ be the array $$$a$$$ sorted in non-descending order.
  • The weight of $$$a$$$ is then defined as $$$\displaystyle \sum_{i=1}^{n} \left\lfloor{\frac{b_i \cdot i^k}{w}}\right\rfloor$$$.

Here, $$$\left\lfloor x \right\rfloor$$$ is the largest integer not exceeding $$$x$$$.

For example, if $$$k = 2$$$ and $$$w = 3$$$, then the weight of $$$a = [3, 2, 2]$$$ is equal to:

$$$\displaystyle \left\lfloor {\frac{2 \cdot 1^2}{3}} \right\rfloor + \left\lfloor {\frac{2 \cdot 2^2}{3}} \right\rfloor + \left\lfloor {\frac{3 \cdot 3^2}{3}} \right\rfloor = 0 + 2 + 9 = 11$$$.

You are given an initial array $$$a$$$, and will be given $$$q$$$ queries. Each query changes one element of array $$$a$$$. After each query, you should output the new weight of the array. Since array weights can be really large, you should output them modulo $$$998\,244\,353$$$.

Note that the changes persist between queries. For example, the second query is applied to the array which is already changed by the first query.

Input

The first line contains three integers $$$n$$$, $$$k$$$, $$$w$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 5$$$, $$$1 \le w \le 5$$$): the length of the array and the parameters from the statement.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 10^5$$$): the elements of the original array.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$): the number of queries.

Each of the next $$$q$$$ lines contains two integers, $$$\mathit{pos}$$$ and $$$x$$$ ($$$1 \le \mathit{pos} \le n$$$, $$$0 \le x \le 10^5$$$). This describes a query that changes $$$a_{\mathit{pos}}$$$ into $$$x$$$.

Output

Output $$$q$$$ integers: the weights of the array after each change, modulo $$$998\,244\,353$$$.

Examples
Input
3 1 1
2 2 8
2
2 5
3 6
Output
36
30
Input
4 2 2
1 3 3 7
4
1 1
2 4
3 8
4 8
Output
75
80
103
108