A tower of n disks (disk 1 smallest, disk n largest) starts stacked on spire 0 and is relocated to spire 2 using spire 1 as spare, via the standard optimal 2^n - 1-move recursion (relocate top n-1 to the spare, move disk n, relocate the n-1 onto disk n).
After exactly k moves have been performed (0 <= k <= 2^n - 1), report the contents of each spire. The intended approach determines each disk's spire recursively without replaying all k moves one by one.
Input format
A single line with two integers: n k.
Output format
Exactly three lines, one per spire in the order spire 0, spire 1, spire 2. Each line lists that spire's disks from bottom to top (largest to smallest), space-separated. Print an empty line for a spire that holds no disks.
Constraints
- 1 <= n <= 20
- 0 <= k <= 2^n - 1