Triangular Museum 

A museum has K² triangular rooms, where ( $0 \leŸ K \leŸ 10$). All rooms have the same size and there is exactly one guard in each room. The shape of the museum itself is also triangular, as exemplified in Figure 1, where a museum with 3² triangular rooms is shown. The names AA, BB, CC, ... are guard names (a guard name is a sequence of at most 10 letters). Thus guard DD is at the top room of the initial configuration presented in Figure 1.

Each two adjacent rooms are separated by exactly one wall, which has a door that connects the rooms. Since the guards would also like to appreciate the art in the museum, they agree to exchange their positions, thus forming a new configuration, previously agreed upon. The order in which the guards move to their new positions obey a few rules. These rules, for security reasons, do not allow guards to leave their positions all at the same time. The only way they can move is by exchanging their positions with guards in adjacent rooms, one pair at a time.

The objective of this problem is to find a sequence of exchanges between guards that leads to the new configuration.

       Initial Configuration         New Configuration
               /\                           /\
              /DD\                         /AA\
             /———____—\                       /____————\
            /\    /\                     /\    /\
           /FF\AA/CC\        ===>       /BB\CC/DD\
          /____\————/—____———\                 /—____\———/____\————
         /\    /\    /\               /\    /\    /\
        /BB\EE/II\GG/HH\             /EE\FF/GG\HH/II\
       /____\————/——____——\/————____\           /____————\/____\————/____\————

                           Figure 1.

Input 

The input file may contain several instances of the problem. Each instance consists of two lines: the first contains the integer K; the second line contains the sequence of K² guard names in the initial configuration (from the top to bottom and left to right) followed by the K² guard names in the new configuration (also from the top to bottom and left to right).

There is at least one blank space between these strings of letters. The last line of the input file contains only the value 0 (zero) which should not be processed.

Instances are NOT separated by blank lines.

Output 

For each instance in the input file, the program must write the value N in a line, where N is the number of exchanges performed between guards in adjacent rooms, followed by N lines, N Ÿ< 4K³, each with the names of two guards been exchanged; the names of the guards are separated by a blank space. Two instances are separated by a blank line.

Sample Input 

3
DD FF AA CC BB EE II GG HH           AA BB CC DD EE FF GG HH II
2
D A B C                              A B C D
0

Sample Output 

6
GG II
HH II
EE BB
DD AA
BB FF
DD CC

3
A B
A D
C D