Rotate a Matrix by 90 Degrees In Place

Given a two-dimensional array named matrix, transform it by rotating every entry 90 degrees to the right.

Requirements:

• Perform the transformation directly within the original matrix, using just O(1) additional memory.
• matrix is guaranteed to be a square N x N matrix.

Input Format

• Line one provides the integer N, which is the matrix dimension.
• Each of the following N lines lists N integers that form one row of the matrix.

Output Format

• Display the transformed matrix over N rows, with spaces separating the N values on each row.

Constraints

• 1 <= N <= 200
• Every matrix value can be represented by a signed 32-bit integer.

Example

Input

3
2 4 6
8 10 12
14 16 18

Output

14 8 2
16 10 4
18 12 6

matrix = [[2, 4, 6], [8, 10, 12], [14, 16, 18]]

14 8 2
16 10 4
18 12 6

The bottom row becomes the leftmost column, producing a clockwise quarter-turn.

Example

Input

1
42

Output

42

A matrix containing one element remains unchanged after rotation.