GrandPaPà calls $f(p)$ applied to a permutation $p_1,p_2,\ldots,p_n$ as the number of pairs $(i,j)$ such that $i<j$ and $p_i+1 = p_{j}$. For example, $f([1,2,3]) = 2$, $f([3,1,2]) = 1$ and $f([3,2,1]) = 0$.

Given $n$ and a permutation $p$ of length $n$, we define a permutation $p'$ of length $n$ to be $k$-special if and only if:

1. $p'$ is lexicographically smaller than $p$, and
2. $f(p') = k$.

Your task is to count for each $0 \le k \le n - 1$ the number of $k$-special permutations modulo $m$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

A permutation $a$ of length $n$ is lexicographically smaller than a permutation $b$ of length $n$ if and only if the following holds: in the first position where $a$ and $b$ differ, the permutation $a$ has a smaller element than the corresponding element in $b$.

Input

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 10^9$) — the length of the permutation and the required modulo.

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$.

Output

Print $n$ integers, where the $k$-th integer is the number of $(k-1)$-special permutations modulo $m$.

Example 1

stdin

4 666012
1 3 4 2

stdout

0 0 2 1 

Note

The permutations that are lexicographically smaller than $[1,3,4,2]$ are:

• $[1,2,3,4]$, $f([1,2,3,4])=3$;
• $[1,2,4,3]$, $f([1,2,4,3])=2$;
• $[1,3,2,4]$, $f([1,3,2,4])=2$.

Thus our answer is $[0,0,2,1]$.

Example 2

stdin

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

stdout

0 53 20 32 14 14 32 20 53 1