Yuki is a computer expert!

In the Kiyux system developed by Yuki, users can create several files named with numbers. In this system, $\texttt{ls > NAME}$ is a very interesting command. After executing this command, the system performs the following operations in order:

• If a file named $\texttt{NAME}$ does not exist in the current directory, create a file named $\texttt{NAME}$; if a file named $\texttt{NAME}$ already exists in the current directory, clear the content of that file.
• Write the filenames of all files currently in the directory into the file named $\texttt{NAME}$ in increasing order, separating adjacent filenames with a single space.

For example, after executing $\texttt{ls > 1}$, $\texttt{ls > 2}$, $\texttt{ls > 3}$, and $\texttt{ls > 1}$ in sequence:

• The content of the file named $\texttt 1$ is $\texttt{1 2 3}$, and its size is $5$ bytes (containing $5$ characters);
• The content of the file named $\texttt 2$ is $\texttt{1 2}$, and its size is $3$ bytes (containing $3$ characters);
• The content of the file named $\texttt 3$ is $\texttt{1 2 3}$, and its size is $5$ bytes (containing $5$ characters).

Initially, there are no files in the current directory. Yuki will execute $n$ commands in sequence, where the $k$-th command is $\texttt{ls > }a_k$, with $1 \le a_k \le m$. You need to calculate the size in bytes (i.e., the number of characters) of the file named $i$ for each positive integer $i$ not exceeding $m$.

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers $a_1, \dots, a_n$.

Output a single line containing $m$ integers, where the $i$-th integer represents the size of the file named $i$ (i.e., the number of characters).

Examples

Input 1

4 3
1 2 3 1

Output 1

5 3 5

Note

This example is the same as the one provided in the problem description.

Input 2

11 10
3 7 1 5 2 4 9 3 8 10 6

Output 2

5 9 13 11 7 20 3 15 13 18

Note

After executing the $11$ commands in sequence:

• The content of the file named $\texttt 1$ is $\texttt{1 3 7}$, and its size is $5$ bytes (containing $5$ characters);
• The content of the file named $\texttt 3$ is $\texttt{1 2 3 4 5 7 9}$, and its size is $13$ bytes (containing $13$ characters);
• The content of the file named $\texttt 6$ is $\texttt{1 2 3 4 5 6 7 8 9 10}$, and its size is $20$ bytes (containing $20$ characters).

Input 3

(list/list3.in)

Output 3

(list/list3.ans)

Note

This test case satisfies the constraints of test point $5$.

Input 4

(list/list4.in)

Output 4

(list/list4.ans)

Note

This test case satisfies the constraints of test point $7$.

Input 5

(list/list5.in)

Output 5

(list/list5.ans)

Note

This test case satisfies the constraints of test point $8$.

Input 6

(list/list6.in)

Output 6

(list/list6.ans)

Note

This test case satisfies the constraints of test point $10$.

For all test data:

• $1 \le m \le n \le 5\times10^5$;
• $1 \le a_i \le m$;
• After executing the $n$ commands in sequence, it is guaranteed that for every positive integer $i$ not exceeding $m$, the file named $i$ exists.

Special Property: Guaranteed $m=n$.