domnulT

Time limit: 2.5s Memory limit: 256MB Input: domnult.in Output: domnult.out

Enunț

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

Cerință

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

Date de intrare

Fișierul de intrare domnult.in conține pe prima linie trei numere naturale n,m,pn, m, p. Pe a doua linie se vor afla nn numere naturale, v1,v2,...,vnv_1, v_2, ..., v_n, reprezentând elementele șirului vv. Pe a treia linie se va afla un număr natural qq reprezentând numărul de operații. Pe următoarele qq 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 11.

Restricții și precizări

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

Exemplu

domnult.in

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

domnult.out

36
3

Log in or sign up to be able to send submissions!