Bruteforce

고정된 정수 $k$와 $w$가 주어진다.

길이 $n$인 배열 $a$의 가중치를 다음과 같이 정의한다.

• $b$를 $a$를 오름차순으로 정렬한 배열이라 하자.
• $a$의 가중치는 $\displaystyle \sum_{i=1}^{n} \left\lfloor{\frac{b_i \cdot i^k}{w}}\right\rfloor$로 정의된다.

여기서 $\left\lfloor x \right\rfloor$는 $x$를 넘지 않는 가장 큰 정수이다.

예를 들어 $k = 2$이고 $w = 3$이면 $a = [3, 2, 2]$의 가중치는 다음과 같다.

$\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$.

초기 배열 $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$개 줄에 각각 두 정수 $\mathit{pos}$와 $x$가 주어진다 ($1 \le \mathit{pos} \le n$, $0 \le x \le 10^5$). 이는 $a_{\mathit{pos}}$를 $x$로 바꾸는 질의를 나타낸다.

각 변경 후 배열의 가중치를 $998\,244\,353$으로 나눈 나머지를 $q$개 출력한다.