409831: GYM103800 H Ginger's clone

There is a matrix of size $$$n \times n$$$, each cell of the matrix has a number. Initially, Ginger stands in the upper left grid and the initial direction is downward, and Ginger's clone is in the lower right grid and the initial direction is upward.

Ginger and his clone will continue to walk in one direction, until the next grid is walked or beyond the matrix range, will turn 90° to the left and change direction to continue walking.

Finally, output the numbered sequence that Ginger and the clone walked through.

Note that if Ginger and his clone walk to a grid at the same time, the number of the grid is regarded as Ginger walking, not Ginger's clone.

The first line contains a integer $$$n$$$ $$$(2 \le n \le 200)$$$ indicating side length of square matrix.

The next line, contains the matrix of size $$$n \times n$$$, indicating the number of each grid (there is no grid with the same number in the matrix, and guarantee the number must be in the range of positive integers).

The output consists of two lines. The first line represents the number sequence of Ginger's walk, and the second line represents the number sequence of the clone's walk.

3
1 2 3
4 5 6
7 8 9

1 4 7 8 5 
9 6 3 2 

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

1 5 9 13 14 15 11 7 
16 12 8 4 3 2 6 10 

In test case $$$1$$$, Ginger and the clone will arrive at the grid numbered $$$5$$$ at the same time, which is regarded as Ginger.