Tần suất theo phần dư modulo m (Frequency by Remainder Modulo m)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ số nguyên không âm $a_1,a_2,\ldots,a_n$ và số nguyên dương $m$.

Với mỗi $r\in\{0,1,\ldots,m-1\}$, đặt

Hãy tính toàn bộ $m$ tần suất $c_0,c_1,\ldots,c_{m-1}$.

Input

• Dòng 1 chứa hai số nguyên $n,m$.
• Dòng 2 chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In $m$ số nguyên $c_0,c_1,\ldots,c_{m-1}$ trên một dòng.

Subtask

Subtask 1 (20 điểm): $1\le n\le 50$, $1\le m\le 10$, $0\le a_i\le 1000$.

Subtask 2 (30 điểm): $1\le n\le 5000$, $1\le m\le 100$, $0\le a_i\le 1000000$.

Subtask 3 (50 điểm): $1\le n\le 100000$, $1\le m\le 1000$, $0\le a_i\le 1000000000$.

Ví dụ

Input

7 4
0 1 2 3 4 8 11

Output

3 1 1 2

Giải thích

Theo modulo 4, các phần dư 0,1,2,3 xuất hiện lần lượt 3,1,1,2 lần.