Background

As everyone knows, Little c is an expert at Happy Match-3, while Little z is not good at games that require even a bit of thinking. During the May Day holiday, Little c was bored and decided to teach Little z.

After five days and five nights of nonstop teaching, Little z finally understood a little (Little z thinking: if only I could be even a little passionate about learning probability theory...). However, both of them ignored the fact that this game is addictive. More importantly, Little z is from Shandong, so he decided to add some hometown flavor...

Little z: “...As everyone knows, Dezhou is in Shandong, so let’s call it ‘Texas Match-3’!”

Little c quickly stopped him: Just forget it. Did you forget that last messy mixed-up board? Besides, this “Texas” is not that “Texas”! If you want to do it, do it yourself—don’t drag me into it.

Before he even finished speaking, Little z threw the rules at Little c.

Little c: “Sounds good.”

Problem Description

Given a board of size $n \times m$, with the top-left corner at $(1,1)$ and the bottom-right corner at $(n,m)$. There are $k$ different colors of pieces, with color IDs $1 \sim k$. Initially, every cell contains one piece.

There are $q$ operations. Each operation swaps two adjacent pieces (adjacent in the up, down, left, or right direction). After that, any consecutive segment of at least $3$ pieces of the same color in the same row or the same column will be eliminated.

After elimination, all pieces fall due to gravity, and the top of each column becomes empty. After all falling finishes, if there is another eliminable situation, it will trigger a chain reaction and continue eliminating, until no more eliminations are possible. Call one elimination plus one falling “one elimination round”, and thus define the number of elimination rounds triggered by an operation.

Some pieces have special attributes. When eliminated, they trigger special effects. There are $6$ types:

• 1: When eliminated, eliminate all pieces in the same row.
• 2: When eliminated, eliminate all pieces in the same column.
• 3: When eliminated, eliminate all pieces in the same row and the same column.
• 4: When eliminated, eliminate all pieces in the $3 \times 3$ square centered at it.
• 5: When eliminated, eliminate all pieces in the $5 \times 5$ square centered at it.
• 6: When eliminated, eliminate all pieces with the same color as it.

When triggering a piece’s special effect, it may chain-trigger other pieces’ special effects, but all of these are triggered within the same elimination round (i.e., during the chain reaction, no falling is caused).

In the game, every operation is required to be valid: the two positions must be adjacent and neither may be empty, and after the operation, eliminations must occur. If an operation is not valid, skip it directly. The game ends after all $q$ operations are processed.

Define the “main color” of a valid operation as the color(s) that are eliminated directly due to the swap (excluding eliminations caused by special effects and falling). It is easy to see that a valid operation has at least $1$ main color and at most $2$ main colors.

In the game, the player wants to obtain as many points as possible through operations. The scoring rules consist of $5$ parts: elimination points + chain points + combo points + hand points + endgame points.

• Elimination points: In each valid operation, the elimination points of the $i$-th elimination round equal $i$ times the sum of the color IDs of all pieces eliminated in that round.

• Chain points: Suppose a valid operation has a total of $x$ elimination rounds, then the chain points are $80(x-1)^2$.

• Combo points: In a certain elimination round, considering only eliminations triggered by “at least $3$ consecutive pieces of the same color in the same row or column” (i.e., not considering any eliminations caused by special effects), let the size of a 4-connected same-color component eliminated be $x$, then the combo points are $50(x-3)^2$. For example: a 4-in-a-row component scores $50$, a 5-in-a-row, cross, or T shape scores $200$, and a $2\times3$ square of the same color scores $450$.

• Hand points: Every $5$ valid operations, compute hand points once. Take the main colors of the previous $5$ valid operations (if an operation has multiple main colors, choose the main color that yields the maximum score according to the rules below), and score according to the following hand rules:

  • High card: all $5$ colors are different, score $50$ points + the maximum color ID among the five.
  • One pair: $2$ of the same color + $3$ different colors, score $100$ points + (pair color ID) $\times 2$.
  • Two pairs: $2$ pairs + $1$ other color, score $200$ points + (larger pair color ID) $\times 2$ + (smaller pair color ID).
  • Three of a kind: $3$ of the same color + $2$ different colors, score $300$ points + (triplet color ID) $\times 3$.
  • Full house: $3$ of the same color + another $2$ of the same color, score $500$ points + (triplet color ID) $\times 3$ + (pair color ID).
  • Four of a kind: $4$ of the same color + $1$ other color, score $750$ points + (four-of-a-kind color ID) $\times 5$.
  • Five of a kind: all $5$ colors are the same, score $1000$ points + (five-of-a-kind color ID) $\times 10$.

• Endgame points: If all $q$ operations are valid, gain an additional $1000$ endgame points when the game ends. If the board is completely cleared when the game ends, gain an additional $10000$ endgame points.

Given the initial state of a game and the player’s operations, you need to compute the player’s total score.

Input Format

Line $1$: $4$ positive integers $n,m,k,q$.

Next $n$ lines: each line has $m$ positive integers $a_{i,j}$, representing the color of the piece in the initial state, in row $i$ from top to bottom and column $j$ from left to right.

Next $n$ lines: each line has $m$ non-negative integers $b_{i,j}$, representing the special effect of the piece in the initial state, in row $i$ from top to bottom and column $j$ from left to right, as described in the statement. In particular, $b_{i,j}=0$ means there is no special effect.

Next $q$ lines: each line has $4$ positive integers $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$, representing swapping the pieces at coordinates $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$.

Output Format

Output one line with a non-negative integer, representing the total score at the end of the game.

8 8 5 5
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 1 4
3 2 4 2
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8

11692

8 8 5 8
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0
1 1 2 2
3 2 4 2
3 2 3 3
4 2 4 3
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8

684

5 5 2 1
1 1 2 1 1
1 1 2 1 1
2 2 1 2 2
1 1 2 1 1
1 1 2 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3 4 3

3023

Hint

[Sample 1 Explanation]

After each operation, the sums of the first $3$ types of points are: $315,\ 417,\ 429,\ 435,\ 482$. After the 5th operation, compute the hand points. The best hand is $(1\ 2\ 4\ 2\ 4)$, and the score is $200 + 4\times 2 + 2 \times 1 = 210$. At the end, both endgame bonuses can be obtained, so the total score is $11692$.

[Sample 2 Explanation]

Compared with the previous sample, $3$ invalid operations are added, and it is impossible to clear the board at the end, so no endgame points can be obtained.

[Constraints and Notes]

$n,m\leq 50,\ k \leq 100,\ q \leq 1000,\ a_{i,j} \leq k,\ b_{i,j} \leq 6,\ x_{i,1},x_{i,2} \leq n,\ y_{i,1},y_{i,2} \leq m$.

It is guaranteed that in the initial state there is no situation that can be eliminated directly.

Translated by ChatGPT 5