Andy is travelling through the galaxy. His mission is to categorize the planets that he passes. There are $K$ types of planets. He passes by $N$ different planets. Each of these planets can be classified as one of these $K$ types. You would like to help Andy on his mission by programming a computer assistant for him. Whenever he passes a planet, he will tell the assistant the type of this planet. The assistant must then tell him how many previous planets are of this type. At the end of his journey, the assistant must also report the total different types of planets that he has passed by.

Input Specification

Line $1$: $N$ and $K$, separated by a single space.

Line $2$ to $N+1$: $a_i$, the type of the planet that he has passed, where $i+1$ is the line number.

Output Specification

Line $1$ to $N$: $b_i$, the number of previous planets that are of type $a_i$, where $i$ is the line number.

Line $N+1$: $t$, the total number of different types of planets that Andy has passed.

Constraints

$1\le N\le {10}^5$

$1\le K\le {10}^9$

$1\le a_i\le K$

Subtasks

Subtask 1 [10%]

$N\le 1000$

Subtask 2 [10%]

$K\le {10}^6$

Subtask 3 [80%]

No additional constraints.

Sample Input

5 4
1
4
4
3
4

Sample Output

0
0
1
0
2
3