Matrix Rotation

You are given an n x n square matrix. Your task is to rotate this matrix 90° clockwise in-place. In other words, modify the input matrix so that after rotation, the matrix elements are rearranged according to the following transformation:

$$ A_{rotated}[i][j] = A[n-1-j][i] $$

Note: Although the rotation is performed in-place, for the purpose of input/output, you should read an n x n matrix and then output the rotated matrix.

Example:

Input:
3
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3

inputFormat

The first line contains an integer n (1 ≤ n ≤ 1000) denoting the size of the matrix. Each of the next n lines contains n space-separated integers representing the rows of the matrix.

outputFormat

Output the rotated matrix in n lines. Each line should contain n space-separated integers representing the row of the rotated matrix.## sample

3
1 2 3
4 5 6
7 8 9

7 4 1
8 5 2
9 6 3