Marytone Contest | domnulT

Enunț

T. Zahlentheoretische, domnul T, fiind netetist$^1$, este scurt și la obiect, astfel vă cere să rezolvați următoarea problemă.

Cerință

Se dau trei numere $n, m, p$ și un șir $v$ având $n$ termeni, iar $0 \leq v_i \leq p$.
Domnul T vă cere să procesați $q$ operatii de forma:
1 k: Se cere să numărați câte șiruri $w$ de n termeni, unde $0 \leq w_i \leq p$, sunt strict mai mici lexicografice decât $v$ și au suma elementelor $s$, iar $s \equiv k$ (mod m). Numărul de șiruri fiind foarte mare se cere restul împărțirii lui la $998244353$.
2 x y: Mai grav! Domnul T va modifica valoarea elementului $v_x$ la $y$.

Date de intrare

Fișierul de intrare domnult.in conține pe prima linie trei numere naturale $n, m, p$. Pe a doua linie se vor afla $n$ numere naturale, $v_1, v_2, ..., v_n$, reprezentând elementele șirului $v$. Pe a treia linie se va afla un număr natural $q$ reprezentând numărul de operații. Pe următoarele $q$ linii se va afla descrierea pentru fiecare operație.

Date de ieșire

Fișireul de ieșire domnult.out conține o linie cu răspunsurile pentru fiecare operație de tipul $1$.

Restricții și precizări

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 32$
• $1 \leq p \leq 10^9$
• $1 \leq q \leq 10^4$
• netetist$^1$ este persoana care lucrează la compania Nu Tulbura Timpul.
• Pentru teste în valoare de $20p$, se procesează doar o operație de tip $1$.

Exemplu

domnult.in

3 3 9
1 0 9
3
1 2
2 1 0
1 0

domnult.out

36
3