회전 격자판

NYPC 2018 · 예선

회전 격자판은 N×NN\times N개의 정사각형이 NNNN열로 나누어져 있으며, 각 칸에 양의 정수가 저장되어 있다. ii번째 행의 jj번째 열에 저장된 정수를 a[i][j]a[i][j]라고 하자.

회전 격자판은 한 번의 동작에 다음을 수행한다.

for (i = 1; i <= N; i++)
  for (j = 1; j <= N - 1; j++)
    if (a[i][j] > a[i][j + 1])
      a[i][j]a[i][j + 1]의 값을 서로 바꾼다
회전 격자판을 반시계 방향으로 90도 회전한다

예를 들어, N=4N=4일 때, 다음의 회전 격자판을 한 번 동작시키면 격자판의 값이 다음과 같이 변화한다.

주어진 회전 격자판을 TT번 동작하고 난 후 격자판에 저장된 값들을 출력하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 격자판의 행의 개수(=열의 개수)를 나타내는 정수 NN(1N3001 \le N \le 300)과 격자판의 동작 횟수를 나타내는 TT(1T1091 \le T \le 10^9)가 주어진다.

다음 이어지는 NN개의 줄의 ii번째 줄에는 초기 격자판의 ii번째 행의 값들을 나타내는 정수 a[i][1]a[i][1], a[i][2]a[i][2], \cdots, a[i][N]a[i][N](1a[i][j]1091 \le a[i][j] \le 10^9)이 공백을 사이에 두고 주어진다.

출력 형식

회전 격자판이 TT번 동작 한 후, 격자판에 저장된 값들을 NN개의 줄에 출력한다. NN개줄의 ii번째 줄에는 격자판의 ii행의 값들을 나타내는 정수들을 공백 하나를 사이에 두고 출력한다.

예제 1

입력

4 1 3 2 5 3 5 4 6 1 9 5 7 3 6 8 3 4

출력

5 6 9 8 3 1 3 4 3 5 7 3 2 4 5 6

예제 2

입력

4 2 3 2 5 3 5 4 6 1 9 5 7 3 6 8 3 4

출력

9 4 7 6 8 3 3 5 6 3 5 4 5 1 3 2

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 100

T300T \le 300

종류 2: 50

별다른 제약조건 없음.

해설