Bruteforce

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

For an array $a$ of length $n$, its weight is defined as follows.

• Let $b$ be the array $a$ sorted in non-descending order.
• The weight of $a$ is $\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

$\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 then $q$ queries. Each query changes one element of array $a$. After each query, output the new weight of the array. Array weights can be very large, so output them modulo $998\,244\,353$.

Changes persist between queries. For example, the second query is applied to the array 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 weight of the array after each change, modulo $998\,244\,353$.