This page is still under construction.

Parts of this page are still being built. What you see may change.

Rotating the Grid

Time limit2sMemory limit1024 MB

Summary
Maintain an N x N grid under clockwise rotations of nested square rings, clockwise 2x2 swaps, and point queries of the value at a cell.
Level

Medium7 of 10

Topics
Implementation, Simulation, Array, Matrix
Solved
No attempts yet

Problem

Taeyoung likes grids. So he built an N × N grid made of conveyor belts. Each cell can be written as (r, c), where r is the number of the row counting from the top and c is the number of the column counting from the left. Each cell holds one number.

The grid Taeyoung built consists of several conveyor belts nested from the outside inward. Consider an 8 × 8 grid as an example.

Cells of the same color belong to the same conveyor belt.

Hoseok hates grids, and he wants to spin Taeyoung's grid around wildly. What is more, after spinning it around he even asks which number sits in which cell. Hoseok's actions come in three kinds.

  • The input gives 1 a b. Rotate the conveyor belt at position a from the outside clockwise by b cells.
  • The input gives 2 c d. Change the 2 × 2 square made of the four cells (c, d), (c, d + 1), (c + 1, d), (c + 1, d + 1) into the shape obtained by rotating it clockwise by one cell. This action does not affect the conveyor belts, only the numbers placed on them. For example, if the numbers 1, 2, 3, 4 were placed in that order, they end up placed in the order 3, 1, 4, 2.
  • The input gives 3 e f. Ask for the number placed on cell (e, f). Taeyoung must answer this question correctly.

Help Taeyoung answer Hoseok's questions.

Input

The first line gives a positive integer N, the size of the grid, and M, the number of Hoseok's actions.

Lines 2 through N + 1 each give N positive integers separated by spaces. The y-th integer on line x + 1 is the number placed on cell (x, y) of the grid.

Lines N + 2 through N + M + 1 each give three integers separated by spaces that describe Hoseok's actions in the order he performs them.

Output

For each time Hoseok performs action 3, print the corresponding answer, one per line.

Constraints

  • 2 ≤ N ≤ 2,000 (N is even.)
  • 1 ≤ M ≤ 500,000
  • 1 ≤ a ≤ N / 2
  • 1 ≤ b ≤ 100,000
  • 1 ≤ c, d ≤ N - 1
  • 1 ≤ e, f ≤ N
  • 0 ≤ (number on the grid) ≤ 100,000

Examples1

  1. Example 1

    Input
    6 5
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
3 1 1
1 1 1
3 1 1
2 1 1
3 1 1
    Expected output
    0
6
12