Problem 1886: D. Doping 2

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:

$p'$ is lexicographically smaller than $p$ , and
$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