Una imagen es una matriz de \(n \times n\) enteros. Rótala \(90\) grados en el sentido de las agujas del reloj.

Seguimiento: hazlo en el lugar, sin una segunda matriz: con \(O(1)\) memoria extra.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 500)\). Siguen \(n\) líneas con \(n\) enteros cada una, de valor absoluto a lo más \(1000\).

Salida

La matriz rotada, en \(n\) líneas de \(n\) enteros.

Ejemplo 1

Entrada

3
1 2 3
4 5 6
7 8 9

Salida

7 4 1
8 5 2
9 6 3

Ejemplo 2

Entrada

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

Salida

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