Sandor

Hajrá Szentgyörgy, hajrá Sepsi!

Se dă un șir $v$ cu $N$ elemente în ordine descrescătoare și un număr natural $G$.

Se aplică algoritmul lui Sándor pe acest șir, implementarea sa în pseudocod fiind scrisă mai jos:

Algoritmul lui Sándor

Dându-se N, G, v[1], v[2], ..., v[N]
s <- 0
pentru i <- de la 1 la N execută
	dacă s + v[i] <= G atunci
		s <- s + v[i]

Rezultatul aplicării algoritmului lui Sándor este valoarea variabilei $s$ la finalul execuției.

Cerință

Pentru un set de date de intrare $N$, $G$ și $v$ ale algoritmului lui Sándor, se dă un număr $T$ (egal cu $1$ sau $2$). Vom considera toate modurile în care se pot elimina $T$ elemente din șirul $v$. De exemplu, dacă avem șirul $v = [7, 6, 4, 2, 1]$, pentru $T=1$ o eliminare posibilă este a elementului de pe poziția $3$, în urma căreia obținem șirul $v' = [7, 6, 2, 1]$.

Considerăm un șir $f$ cu $G+1$ valori, ($f_0$, $f_1$, \ldots, $f_G$). Valoarea lui $f_i$ este egală cu numărul de moduri de a elimina exact $T$ elemente din șirul $v$ pentru a obține un șir $v'$, pentru care rezultatul aplicării algoritmului lui Sándor pentru $N$, $G$ și $v'$ este egal cu $i$.

Date de intrare

Pe prima linie a fișierului de intrare sandor.in se găsește un număr natural $T$, cu semnificația din enunț. Pe a doua linie se găsesc numerele naturale $N$ și $G$, separate printr-un spațiu. Pe a treia linie se găsesc $N$ numere naturale reprezentând valorile elementelor șirului $v$, al $i$-lea dintre acestea fiind valoarea lui $v_i$ ($1 \leq i \leq N$).

Date de ieșire

În fișierul de ieșire sandor.out se vor afișa $G + 1$ valori $f_0$, $f_1$, \ldots, $f_G$, separate printr-un spațiu, cu semnificația din enunț.

Restricții și precizări

• $1 \leq T \leq 2$;
• $1 \leq N \leq 400 \ 000$;
• $1 \leq G \leq 800 \ 000$;
• $1 \leq v_i \leq G$;
• Pentru $T = 1$, se va elimina un element de pe poziția $i$, cu $1 \leq i \leq N$. Două moduri de a elimina $1$ element se consideră distincte dacă pozițiile elementului eliminat în cele două moduri sunt distincte.
• Pentru $T = 2$, pozițiile eliminate vor fi de forma $(i, j)$, cu $1 \leq i < j \leq N$. Două moduri de a elimina $2$ elemente $(i_1, j_1)$ și $(i_2, j_2)$ se consideră distincte dacă $i_1 \neq i_2$ sau $j_1 \neq j_2$.

Exemplul 1

sandor.in

1
4 11
10 7 3 1

sandor.out

0 0 0 0 0 0 0 0 0 0 1 3 

Explicație

După eliminarea unui element, $s$ poate atinge valoarea $10$ o dată și valoarea $11$ de trei ori.

Exemplul 2

sandor.in

2
4 11
10 7 3 1

sandor.out

0 0 0 0 1 0 0 0 1 0 3 1 

Explicație

După eliminarea unei perechi de două numere, $s$ poate atinge valoarea $4$ o dată, valoarea $8$ o dată, valoarea $10$ de $3$ ori și valoarea $11$ o dată.

Exemplul 3

sandor.in

1
7 20
4 4 4 2 2 1 1

sandor.out

0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 2 2 0 0 0 

Explicație

Observați că elementele șirului $v$ pot fi egale.