This is an answer-submission problem.

Xiao Xiu and Xiao Dong are cooperating to play a game.

Xiao Xiu will randomly receive an integer from $[0, m-1]$ and then enter a room.

There are $n$ lights in the room arranged in a row. Before Xiao Xiu enters the room, the lights are set to a random state, and neither Xiao Xiu nor Xiao Dong knows the state of the lights in advance.

After entering the room, Xiao Xiu can toggle the switch of at most one light to change its state, or she can choose not to change any. Then, she leaves the room without communicating with Xiao Dong.

Next, Xiao Dong needs to enter the room, observe the state of the lights, and guess which number Xiao Xiu received. If he guesses correctly, they win.

Before the game begins, Xiao Xiu and Xiao Dong need to agree on a plan. The plan consists of what number Xiao Dong will guess for every possible state of the lights, and Xiao Xiu's strategy is to make Xiao Dong's guess correct as often as possible.

Please help them design a plan that maximizes the number of winning scenarios.

Input

The input contains three integers $n, m, p$, where $n$ and $m$ are as defined above, and $p$ represents the score for this test case.

Output

Output a single line containing $2^n$ integers, where the $i$-th integer represents the number Xiao Dong will guess when the state of the lights, represented as a binary number, is $i-1$.

Examples

Input 1

3 3 1

Output 1

0 0 1 2 2 1 0 2

Subtasks

If your plan is invalid, you will receive 0 points.

If your plan wins for all $2^n \cdot m$ possible scenarios, you will receive $p$ points.

Otherwise, let $c$ be the total number of scenarios in which your plan does not win. Your score will be $\frac{p}{1.05^{c}}$.