Frequency by Remainder Modulo m

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

You are given $n$ non-negative integers $a_1,a_2,\ldots,a_n$ and a positive integer $m$.

For every $r\in\{0,1,\ldots,m-1\}$, define

Compute all frequencies $c_0,c_1,\ldots,c_{m-1}$.

Input

• The first line contains $n,m$.
• The second line contains $a_1,a_2,\ldots,a_n$.

Output

Print $c_0,c_1,\ldots,c_{m-1}$ separated by spaces.

Subtasks

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

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

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

Example

Input

7 4
0 1 2 3 4 8 11

Output

3 1 1 2

Explanation

Modulo 4, remainders 0,1,2,3 occur 3,1,1,2 times respectively.