You are requirea to design an algorithm which solves the Tower of Hanoi puzzle (see the figure below). You have an array of stacks (use the ListStack implementation) named rods with size 3 All three of the stacks are in the same size which is n At the b rods (first stack) is full of discs marked with positive integers from 1 to n where 1 is at the top and n s at the bottom (i.e, you need three stacks of Integers with the first initialized to store the n Integers). The other two stacks are empty. The al of the puzzle: is to move all these disks from rodsloj to the third rod, rods(2], with the help of rods without breaking any rules ofthe Tower of Hanoi puzzle. The rules of the Only one disc may be moved at a time Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod No disk may be placed on top of a smaller disk. Hints: To move a stack of k discs from rod A to rod B, we first move k-1 discs from A to C, then move the remaining (kth) disc from rod A to B, and then finally move all k-1 discs on C to B. Also, if you closely examine the puzzle you will see that there is at most one legal move between any two rods. Deliverables: TowersofHanoi.j A class that has the rods, and the size n of the storage of the rods. It has a constructor that takes the towercapacity( i.e., n) and creates the new array rods, (i.e., Stack Integer ll rods new Arraystack 31; It then initializes the three stacks (each with capacity n) with the first rod containing the n integers. Implements Boolean legalMove(int a, int b) returns true if it is legal to move a disc from rod a to rod b. (rods are referred to as rod 0, rod 1, rod 2) Implements Boolean move (int a, int b) that moves a disc from a to b after ensuring it is a legal move and prints out a sentence disc x moved from rod y to rod z" with x,y, z representing the right number for the disc and the rods. It returns false if the move is not legal. Implements Boolean move int m, int a, int b, int c) moves m discs from tower a to tower b using tower c as an intermediate storage. It prints out all the movements of the discs as they appear. It returns false if the moves are not legal. This could be because a doesn t have m discs, rod b has exceeded capacity or you are trying to store a large disc on top of a smaller one Implement the method void show TowerStates() prints out the contents of the rods