Rotate Image

Given an n x n matrix, rotate it 90° clockwise in place — O(1) extra space, no second matrix.

Example

Input:

Output:

Approach

Two clean, in-place passes instead of one clever-but-fiddly direct rotation: first transpose the matrix (swap grid[i][j] with grid[j][i] for every i < j, flipping it across its main diagonal), then reverse every row. Transpose-then-reverse-rows is exactly a 90° clockwise rotation, and both steps are trivially in-place.

Input format

Line 1: n Next n lines: n space-separated integers

Print the rotated matrix, one row per line, space-separated.