One Move from Towers of Hanoi#6623

One Move from Towers of Hanoi

1 second

64 megabytes

Very easy

You are given the classic Towers of Hanoi problem:

There are three posts and $n$ circular disks of distinct sizes ( $1$ denotes the smallest disk, $n$ the largest). The disks start stacked on post $A$ , and the goal is to move the entire stack to post $C$ . At each step, you may move one disk from the top of one post onto another post, but you may never place a larger disk on top of a smaller one. The posts are named $A$ , $B$ , and $C$ .

A well-known recursive solution to this problem is as follows:

move(num_disks, from_post, spare_post, to_post)
    if (num_disks == 0)
        return
    move(num_disks--1, from_post, to_post, spare_post)
    print("Move disk ", num_disks, " from ", from_post, " to ", to_post)
    move(num_disks--1, spare_post, from_post, to_post)

Given $k$ and $n$ , determine the $k$ -th move performed by this recursion.

Input

Each input line contains two integers $k$ and $n$ . Input ends with a line containing two zeros. All inputs are valid. $k$ and $n$ are positive integers, with $k < 2^{n}$ k < 2^n and $n \leq 60$ n \leq 60.

Output

For each case, output the $k$ -th move in the following format:

Case $x$ : $d$ $f r o m$ $t o$

where $x$ is the test case number (starting from 1), $d$ is the disk number, $f r o m$ is the source post, and $t o$ is the destination post. Use a single space to separate the parts; do not print trailing spaces.

Examples

Example 1