Easy Problem
题号：NC218176
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Output the first M steps in the best strategy of the famous problem - Tower of Hanoi.
-------------------------------
Tower of Hanoi

The Tower of Hanoi consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No larger disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.


输入描述:

One line with 2 integers N, M, representing the numbers of disks and needed steps.

输出描述:

M lines.
For each line, you should output your answer like k:x.a->c.
It means the k-th step moves x-th disk from a to c.
示例1

输入

复制 
3 6

输出

复制 
1:1.1->3
2:2.1->2
3:1.3->2
4:3.1->3
5:1.2->1
6:2.2->3
示例2

输入

复制 
6 20

输出

复制 
1:1.1->2
2:2.1->3
3:1.2->3
4:3.1->2
5:1.3->1
6:2.3->2
7:1.1->2
8:4.1->3
9:1.2->3
10:2.2->1
11:1.3->1
12:3.2->3
13:1.1->2
14:2.1->3
15:1.2->3
16:5.1->2
17:1.3->1
18:2.3->2
19:1.1->2
20:3.3->1

备注:

1 <= n <= 10^4
1 <= m <= 10^7