问题描述

给定一个n x n的二维矩阵matrix，表示一个图像。请你将图像顺时针旋转90度。

• 你必须在原地旋转图像，这意味着直接修改输入的二维矩阵。
• 不要使用额外的矩阵来旋转图像。

格式

输入

• 一个n x n的整数矩阵，每个元素是一个整数。

输出

• 旋转后的n x n整数矩阵。

样例

样例1

输入

3
1 2 3
4 5 6
7 8 9

输出

7 4 1
8 5 2
9 6 3

样例2

输入

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

输出

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

提示

• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000