21322번 - 격자 돌리기

태영이는 격자를 좋아한다. 그래서 컨베이어 벨트로 이루어진 N × N 모양의 격자를 만들었다. 각 칸은 (r, c)로 나타낼 수 있으며 r은 맨 위에서 몇 번째 칸인지 의미하고 c는 맨 왼쪽에서 몇 번째 칸인지 의미한다. 각 칸에는 숫자가 하나씩 올려져 있다.
태영이가 만든 격자는 바깥에서부터 여러 컨베이어 벨트가 중첩되어 있는 형태이다. 8 × 8형태의 격자를 예로 들어보자.

같은 색은 같은 컨베이어 벨트에 포함된다는 것을 뜻한다.

그런데 격자를 싫어하는 호석이는 태영이의 격자를 마구마구 돌려버리려고 한다. 더군다나 격자를 마구마구 돌리고 나서는 어떤 칸에 어떤 수가 놓여있는지 물어보기까지 한다.
호석이의 행동은 3가지로 정리해볼 수 있다.

• 1 a b 가 입력으로 주어진다.
  바깥에서 a번째 위치한 컨베이어 벨트를 시계 방향으로 b칸 만큼 회전시킨다.
• 2 c d 가 입력으로 주어진다.
  (c, d), (c, d + 1), (c + 1, d), (c + 1, d + 1) 4개의 칸으로 이루어진 2 × 2 정사각형을 시계 방향으로 한 칸 회전시킨 모양으로 바꾼다. 이 행동은 컨베이어 벨트에는 영향이 없고 컨베이어 벨트 위에 올려진 수에만 영향이 있다.
  예를 들어, 순서대로 1, 2, 3, 4 의 수가 올려져 있었다면 순서대로 3, 1, 4, 2 의 수가 올려져 있는 형태가 된다.
• 3 e f 가 입력으로 주어진다.
  (e, f) 칸 위에 올려져 있는 수를 물어본다. 태영이는 이 질문에 정확하게 답을 해야 한다.

태영이를 도와 호석이의 질문에 답을 해주자.

1번째 줄에 격자의 크기를 의미하는 양의 정수 N과 호석이의 행동의 개수를 의미하는 M이 주어진다.
2번째 줄부터 N + 1번째 줄까지 각 줄에 N개의 양의 정수가 공백을 사이에 두고 주어진다. x + 1번째 줄의 y번째 정수는 격자의 (x, y) 칸에 올려져 있는 수를 의미한다.
N + 2번째 줄부터 N + M + 1번째 줄까지 각 줄에 호석이의 행동 순서대로 호석이의 행동을 의미하는 3개의 정수가 공백을 사이에 두고 주어진다. 

호석이가 3번 행동을 할 때 마다 거기에 맞는 답을 한 줄에 하나씩 출력한다.

• 2 ≤ N ≤ 2,000 (N은 짝수이다.)
• 1 ≤ M ≤ 500,000
• 1 ≤ a ≤ N / 2
• 1 ≤ b ≤ 100,000
• 1 ≤ c, d ≤ N - 1
• 1 ≤ e, f ≤ N
• 0 ≤ (격자 위의 수) ≤ 100,000