Chessboard Elimination Game Score Calculation

Given an \(n \times m\) chessboard with coordinates \((1,1)\) at the top‐left and \((n,m)\) at the bottom‐right. There are pieces in the board in one of \(k\) colors, numbered \(1 \sim k\). Initially every cell contains a piece. There are \(q\) operations. Each operation consists of swapping two adjacent (up, down, left, or right) pieces. After any swap, if in any row or column there is a contiguous segment of at least 3 pieces of the same color, they are eliminated.

After elimination, all pieces will fall down (gravity acting in each column, so that empty spaces appear at the top). After the falling process finishes, if new eliminations can occur, they trigger additional rounds of elimination (a chain reaction) within the same round (i.e. special effects triggered during the chain do not cause additional falling until the chain is finished). We call one elimination plus falling process a "round elimination". In one operation, there may be several rounds of elimination triggered.

Some pieces have special properties. When eliminated, they trigger one of the following six special effects immediately (and may chain trigger other special effects within the same round):

1. Eliminate all pieces in the same row.
2. Eliminate all pieces in the same column.
3. Eliminate all pieces in both the same row and the same column.
4. Eliminate all pieces in the \(3 \times 3\) square centered at this piece.
5. Eliminate all pieces in the \(5 \times 5\) square centered at this piece.
6. Eliminate all pieces of the same color.

An operation is considered valid if the two positions are adjacent, both are non-empty, and after the swap at least one elimination occurs. If an operation is not valid, it is skipped. For a valid operation, define the "main color(s)" as the color(s) of the pieces that are eliminated directly as a result of the swap (i.e. not including pieces eliminated subsequently from special effects or falling).

The scoring is composed of five parts:

• Elimination Score: In a valid operation, let the \(i\)th round elimination remove pieces whose color numbers sum to \(S\). Then this round contributes \(i \times S\) points.
• Chain Bonus: If an operation has a total of \(x\) elimination rounds, add an extra bonus of \(80(x-1)^2\) points.
• Combination Bonus: In one round, considering only eliminations triggered by a contiguous segment (in a row or column) of at least 3 same-colored pieces (ignoring special effects), for each connected four-neighbor block (of the same color) of size \(x\), add \(50(x-3)^2\) points. For example, a group of 4 in a line gives 50 points, 5 together (in a line, cross, or T shape) gives 200 points, and a 2\(\times\)3 square block of the same color gives 450 points.
• Hand Pattern Bonus: Every 5 valid operations, take the main color from each valid operation (if an operation has multiple main colors, choose the one which yields the highest possible bonus according to the rules below). Then, based on the 5 colors, compute a bonus according to these patterns:
  • High Card: All 5 colors are different. Award \(50 + \max(\text{colors})\) points.
  • One Pair: Two of one color and three all different. Award \(100 + 2 \times (\text{paired color})\) points.
  • Two Pairs: Two pairs plus one extra color. Award \(200 + 2 \times (\text{larger paired color}) + (\text{smaller paired color})\) points.
  • Three of a Kind: Three of the same color plus two different ones. Award \(300 + 3 \times (\text{triple color})\) points.
  • Full House: Three of one color and two of another. Award \(500 + 3 \times (\text{triple color}) + (\text{pair color})\) points.
  • Four of a Kind: Four of one color plus one extra color. Award \(750 + 5 \times (\text{quadruple color})\) points.
  • Five of a Kind: All five colors are the same. Award \(1000 + 10 \times (\text{color})\) points.
• Terminal Bonus: If all \(q\) operations are valid, add an extra 1000 points. If the board is completely cleared at the end, add 10000 points.

Your task is to compute the total score achieved by the player given the initial board and a sequence of operations.

inputFormat

The input begins with three integers \(n\), \(m\), and \(k\) (1-indexed) representing the board dimensions and the number of colors. Then follow \(n\) lines, each with \(m\) integers representing the color of the piece in each cell. It is guaranteed that initially no elimination occurs. Next is an integer \(q\), the number of operations. Each of the following \(q\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) representing the positions of two adjacent pieces to swap.

outputFormat

Output a single integer: the total score of the game.

sample

3 3 3
1 2 3
3 1 2
2 3 1
2
1 1 1 2
2 2 2 3

0