Rotating Disks

Time limit1sMemory limit512 MB

Summary
Simulate T rounds of rotating selected concentric disks, erasing adjacent equal numbers, or adjusting all numbers toward the average, then report the final sum.
Level

Medium4 of 10

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

Problem

Disks with radii 1, 2, ..., N rest on the floor in decreasing order of size, and all of them share the same center. If a disk has radius i, it is called the i-th disk. Each disk has M integers written on it, and the position of the j-th number on the i-th disk is denoted (i, j). The positions satisfy the following.

  • (i, 1) is adjacent to (i, 2) and (i, M).
  • (i, M) is adjacent to (i, M-1) and (i, 1).
  • (i, j) is adjacent to (i, j-1) and (i, j+1). (2 ≤ j ≤ M-1)
  • (1, j) is adjacent to (2, j).
  • (N, j) is adjacent to (N-1, j).
  • (i, j) is adjacent to (i-1, j) and (i+1, j). (2 ≤ i ≤ N-1)

The figure below shows the case N = 3, M = 4.

The disks rotate independently. When disk 2 rotates, the other disks do not rotate. A disk rotates with respect to the positions of the numbers, and after the rotation the positions of the numbers must match those before the rotation.

The figures below show examples of rotating disks.

Rotate disk 1 clockwise by 1 positionRotate disks 2 and 3 counterclockwise by 3 positionsRotate disks 1 and 3 clockwise by 2 positions

We want to rotate the disks T times in total as follows. The rotations are fixed in advance, and the variables used for the i-th rotation are xi, di, ki.

  1. Rotate every disk whose number is a multiple of xi by ki positions in direction di. If di is 0 the direction is clockwise, and if di is 1 the direction is counterclockwise.

  2. If any numbers remain on the disks, find all adjacent pairs of numbers that are equal.

    1. If such pairs exist, erase all adjacent equal numbers from the disks.
    2. If no such pairs exist, compute the average of the numbers on the disks, subtract 1 from every number greater than the average, and add 1 to every number smaller than the average.

After rotating the disks T times, find the sum of the numbers on the disks.

Input

The first line gives N, M, and T.

Starting from the second line, N lines give the numbers on the disks. The j-th number on the i-th line is the number written at (i, j).

The following T lines give xi, di, and ki.

Output

After rotating the disks T times, print the sum of the numbers on the disks.

Constraints

  • 2 ≤ N, M ≤ 50
  • 1 ≤ T ≤ 50
  • 1 ≤ numbers on the disks ≤ 1,000
  • 2 ≤ xi ≤ N
  • 0 ≤ di ≤ 1
  • 1 ≤ ki < M

Examples5

  1. Example 1

    Input
    4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
    Expected output
    30

  2. Example 2

    Input
    4 4 2
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
    Expected output
    22

  3. Example 3

    Input
    4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
    Expected output
    22

  4. Example 4

    Input
    4 4 4
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
3 1 1
    Expected output
    0

  5. Example 5

    Input
    4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2
    Expected output
    26