낱말 퍼즐

여러분은 낱말 찾기 퍼즐을 해 보았는가? 낱말 찾기 퍼즐은 각 칸에 글자가 하나씩 쓰여 있는 일정 크기의 격자에서 연속하는 몇 개의 칸이 이루고 있는 단어를 찾는 퍼즐이다.

영어로 된 낱말 퍼즐의 예시.

낱말 찾기 퍼즐은 퍼즐 하나에서 나올 수 있는 단어의 수가 정해져 있다. 옆 동네 윤우가 41기 학생들에게 공룡 게임을 홍보하는 것을 본 지호는, 공룡 게임에 꿀리지 않을 만큼 재미있는 낱말 찾기 퍼즐을 만들기로 했다. 낱말 찾기 퍼즐을 더 재미있게 만들기 위해서, 지호는 다음과 같은 방법을 생각해 냈다. 퍼즐에서 단어를 더 이상 찾지 못하면, 퍼즐을 가로세로로 잘라 네 조각으로 나눈 뒤 각 조각을 180도 회전시켜서 다시 붙이는 것이다. 이렇게 하면, 한 퍼즐에서 찾을 수 있는 단어의 수가 엄청 많아질 것이다. 지호는 가지고 있던 낱말 찾기 퍼즐을 다 가위로 열심히 자르며 새로운 단어를 찾았다. 그런데, 문제가 생겼다. 지호는 퍼즐을 자를 때마다 가위질하는 것이 귀찮아졌다!

그러나 여기서 포기할 지호가 아니다. 옆 동네 공룡 게임도 컴퓨터로 하는 게임이니까, 낱말 찾기 게임도 컴퓨터로 즐기면 되는 것 아니겠는가? 지호를 도와 몇 번이고 퍼즐을 잘라도 퍼즐이 어떻게 변하는지 구해내는 프로그램을 작성해 보자.

여러분에게는 $Q$개의 질의가 주어질 것이다. 주어지는 질의에 따라서 퍼즐을 잘라서 돌리는 작업을 실행하거나 퍼즐의 상태를 출력하는 프로그램을 작성하여라.

첫째 줄에 정수 $N$, $M$, $Q$가 주어진다. $N$과 $M$은 각각 퍼즐의 행과 열의 개수, $Q$는 주어지는 질의의 개수이다.

둘째 줄부터 $N$개의 줄에 걸쳐 초기 상태의 퍼즐이 주어진다. 각 줄에서는 퍼즐의 각 칸을 이루는 문자 $M$개가 문자열의 형태로 주어진다.

그 다음 줄부터 Q개의 질의가 주어진다. 각 질의는 다음과 같다.

• $1$ $x$ $y$: 퍼즐을 다음과 같이 나누어서, 각 조각을 180도 회전시킨다. ($x$, $y$는 정수이다)

  • $1$행부터 $x$행, $1$열부터 $y$열
  • $1$행부터 $x$행, $y+1$열부터 $M$열
  • $x+1$행부터 $N$행, $1$열부터 $y$열
  • $x+1$행부터 $N$행, $y+1$열부터 $M$열

• $2$ : 현재 퍼즐을 출력한다. 이 쿼리는 1번 이상 75번 이하로 주어진다.

2번 쿼리가 주어질 때마다 N개의 줄에 걸쳐 현재 상태의 퍼즐을 출력한다. 입력 조건과 같이, 각 행의 문자는 길이 $M$의 문자열의 형태로 출력한다.

• $2 \leq N, M \leq 250,000$
• $4 \leq NM \leq 500,000$
• $1 \leq Q \leq 1,000,000$
• $1 \leq x \leq N-1$
• $1 \leq y \leq M-1$
• 퍼즐의 각 칸은 알파벳 소문자 한 개로 이루어져 있다.
• 2번 쿼리는 $1$번 이상, $75$번 이하로 주어짐이 보장된다.