Description

There is an $n \times m$ grid. Initially, each cell has an integer weight. Then there are 2 types of operations:

• Change the weight of a cell.
• Query how many times a specified weight appears in a submatrix.

Input Format

The first line contains two integers $n, m$.

Then follow $n$ lines, each with $m$ integers. In the $(i+1)$-th line, the $j$-th number is the initial weight of cell $(i, j)$.

Then an integer $Q$ is given.

Then there are $Q$ lines, each describing an operation.

Operation 1: A line with four integers $1\ x\ y\ c$, meaning set the weight of cell $(x, y)$ to $c$.

Operation 2: A line with six integers $2\ x_1\ x_2\ y_1\ y_2\ c$, meaning query the number of cells whose weight is $c$ and satisfy $x_1\le x\le x_2, y_1\le y\le y_2$.

Output Format

For each operation 2, output one integer per line in the order they appear, representing the required count.

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

1
2

Hint

Constraints

For $30\%$ of the testdata: $n, m\le 30$, $Q\le 5\times 10^4$.

For $100\%$ of the testdata: $1\le n, m\le 300$, $1\le Q\le 2\times 10^5$.

For operation 1, it is guaranteed that $1\le x\le n$, $1\le y\le m$, $1\le c\le 100$.

For operation 2, it is guaranteed that $1\le x_1\le x_2\le n$, $1\le y_1\le y_2\le m$, $1\le c\le 100$.

Translated by ChatGPT 5