A sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ and an integer $x$ are given.

For each $k=0,1,\cdots,N$, consider a new sequence obtained by inserting one $x$ after the $k$-th position of sequence $A$.

That is,

• If $k=0$, insert $x$ before $A_1$.
• If $1 \le k \le N-1$, insert $x$ between $A_k$ and $A_{k+1}$.
• If $k=N$, insert $x$ after $A_N$.

Let $B^{(k)}$ be the sequence of length $N+1$ obtained in this way. For each $k=0,1,\cdots,N$, print the area of the largest rectangle that is contained in the histogram made from $B^{(k)}$.

The input is given in the following format.

$N\ x$ $A_1\ A_2\ \ \cdots \ A_N$

Print a total of $N+1$ lines.

On the $(k+1)$-th line, print the area of the largest rectangle that is contained in the histogram made from $B^{(k)}$.

• $1 \le N \le 200\,000$.
• $1 \le x \le 10^9$.
• $1 \le A_i \le 10^9$ $(1 \le i \le N)$.