Everybody knows the classical puzzle about Hanoi Towers. There are three rods and one of them has n rings in ascending order of radius, the biggest disk is at the bottom, smallest is at the top. The objective of the puzzle is to move all of the rings to another rod in a minimal number of steps and preserve the disk order. During one step you are allowed to move only one ring and smaller radius rings can only be put on top of bigger radius rings.

You are required to solve modified Hanoi Towers puzzle. You have four rods instead of three. All other rules are left unchanged.