Trace a Nested Accumulation Array (Trace mảng tích lũy lồng nhau)

Source: Programming in C

Version: Phuoc Hung OJ Extended

Problem

Given integers $n$ and $x$, consider an array $b$ of length $n$, indexed from $0$ to $n-1$. Initially,

Then execute the following nested accumulation exactly: for $j=0,1,\ldots,n-1$, and for every $i$ with $0\le i<j$ in increasing order, perform

When $b_j$ is processed, $b_0,\ldots,b_{j-1}$ already contain their updated values. Hence, for $j\ge1$,

Print the final array $b$.

Input

One line contains integers $n$ and $x$.

Output

Print $b_0,b_1,\ldots,b_{n-1}$ on one line.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $|x|\le100$.

Subtask 2 (30 points): $1\le n\le25$, $|x|\le10^4$.

Subtask 3 (50 points): $1\le n\le40$, $|x|\le10^6$.

Example

Input

10 1

Output

1 1 2 4 8 16 32 64 128 256

Explanation

The sample follows the definitions and rules above.