In the simulation of question 1, enqueue all states visited in a priority queue, prioritized by the hamming distance from the original source. In case of a tie, an alphabetically smaller in a row major format has a preference. Dequeue all states as per the priority and print them in a row major format. While printing, ensure that every state is only printed once, irrespective of how many times it occurs in the simulation.   

Sample Input

1

3 3 9

IIT1 IIT2 IIT3 IIT4 IIT5 IIT6 IIT7 IIT8 IIT9

swap IIT1 IIT4

swap IIT3 IIT6

swap IIT6 IIT3

swap IIT1 IIT4

swap IIT8 IIT9

swap IIT1 IIT2

swap IIT1 IIT3

swap IIT1 IIT3

swap IIT1 IIT2

Sample Output

IIT1 IIT2 IIT3 IIT4 IIT5 IIT6 IIT7 IIT8 IIT9

IIT1 IIT2 IIT3 IIT4 IIT5 IIT6 IIT7 IIT9 IIT8

IIT4 IIT2 IIT3 IIT1 IIT5 IIT6 IIT7 IIT8 IIT9

IIT2 IIT1 IIT3 IIT4 IIT5 IIT6 IIT7 IIT9 IIT8

IIT4 IIT2 IIT6 IIT1 IIT5 IIT3 IIT7 IIT8 IIT9

IIT2 IIT3 IIT1 IIT4 IIT5 IIT6 IIT7 IIT9 IIT8