Hano-Sam Tower

Lee Sejeong, who is taking the COSE214 algorithms course, recently learned how to solve the Tower of Hanoi in class. The rules of the Tower of Hanoi are as follows.

• There are 3 pegs, numbered 1, 2, 3 from left to right.
• N disks of distinct sizes are stacked, and a larger disk may not be placed on top of a smaller disk.
• Each disk is numbered from 1 to N, and a larger number means a larger disk.
• Only one disk may be moved at a time, and each move takes 1 second.
• All disks must be moved from peg 1 to peg 3 in the minimum number of moves.
• <1> A disk may be moved freely from any peg to any peg.

Then Samsejeong, who was sitting next to him, wanted to make his own rules and wondered what would happen if the following condition replaced <1>.

• <2> A disk may be moved only to an adjacent peg. (1 ↔ 2 ↔ 3)

Sasejeong, who was on the other side, proposed the following rule.

• <3> A disk may be moved only to the right peg, except that from peg 3 it moves to peg 1. (1 → 2 → 3 → 1)

They named this problem the Hano-Sam Tower. Lee Sejeong honestly did not like these extra conditions, but to fit in, he decided to find out where each disk is after K seconds. Help him.

The first line contains three integers M, N, K separated by spaces.

M is the number of the rule to apply to the Hano-Sam Tower. 1 ≤ M ≤ 3; 1 means the original problem, 2 means Samsejeong's rule, and 3 means Sasejeong's rule.

The ranges of N and K depend on the value of M. The exact ranges are as follows.

• M = 1: 1 ≤ N ≤ 60, 0 ≤ K ≤ 2N-1
• M = 2: 1 ≤ N ≤ 40, 0 ≤ K ≤ 3N-1
• M = 3: 1 ≤ N ≤ 30, 0 ≤ K ≤ $\frac{3+2\sqrt{3}}{6}(1+\sqrt{3})^N+\frac{3-2\sqrt{3}}{6}(1-\sqrt{3})^N-1$

Print N integers a1, a2, ..., aN on the first line, separated by spaces. ai is the number of the peg where disk i is located after K seconds.