Hanoi Tower K

Interview

Time limit1sMemory limit1024 MB

Summary

Given n disks on the first peg, print the peg pair moved at step K in the minimal Tower of Hanoi solution.

Level: Medium6 of 10
Topics: Recursion, Divide and conquer, Math, Implementation
Solved: No attempts yet

Problem

There are three pegs, and n disks of distinct radii are stacked on the first peg. Each disk is stacked in order of decreasing radius. The monks will now move them from the first peg to the third peg according to the following rules.

Only one disk can be moved to another tower at a time.
In any stack, the upper disk must always be smaller than the lower disk.

Write a program that prints the K-th move among the required sequence of moves that performs this task. The number of moves must be minimal.

The figure below is an example with 5 disks.

Input

The first line gives the number of disks N (1 ≤ N ≤ 60) stacked on the first peg and K. Only values of K for which the K-th move exists are given.

Output

On the first line, print two integers A B separated by a space, representing the K-th step. This means moving the topmost disk of tower A to the top of tower B.

Examples5

Example 1
Input
```
3 1
```
Expected output
```
1 3
```
Example 2
Input
```
3 2
```
Expected output
```
1 2
```
Example 3
Input
```
3 3
```
Expected output
```
3 2
```
Example 4
Input
```
3 6
```
Expected output
```
2 3
```
Example 5
Input
```
3 7
```
Expected output
```
1 3
```