23117번 - Bruteforce 다국어

문제

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.

입력

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 $q$ integers: the weights of the array after each change, modulo 998ドル,244円,353円$.

제한

힌트