Polycarpus has a computer with n processors. Also, his computer has n memory cells. We'll consider the processors numbered by integers from 1 to n and that the memory cells are consecutively numbered by integers from 1 to n.

Polycarpus needs to come up with a parallel program model. For each memory cell number i this program must record the value n - i to this cell. In other words, for each cell you've got to find the distance to cell n.

Let's denote the value that is written in the i-th cell as a_i. Initially, a_i = 1 (1 ≤ i < n) and a_n = 0. We will consider that only processor i can write values in the memory cell number i. All processors can read an information from some cell (several processors can read an information from some cell simultaneously).

The parallel program is executed in several steps. During each step we execute the parallel version of the increment operation. Executing the parallel version of the increment operation goes as follows:

1. Each processor independently of the other ones chooses some memory cell. Let's say that processor i has chosen a cell with number c_i (1 ≤ c_i ≤ n).
2. All processors simultaneously execute operation a_i = a_i + a_ci.

Help Polycarpus come up with the parallel program model that is executed in exactly k steps. Calculate the operations that need to be executed. Note that after k steps for all i's value a_i must be equal n - i.