Garden Operations

In this problem, you are given a garden represented by an (n \times m) grid. Each cell in the grid contains a flower, represented by an integer. In addition, you are provided with a list of incompatible flower pairs. Although the incompatible pairs are given as input, they do not affect the queries. You need to process a series of operations on the grid. There are two types of operations:

1. Query: Given an operation of the form Q x y, determine the size of the connected component (using 4-directional connectivity: up, down, left, right) of cells having the same flower type as the cell at row (x) and column (y). Note that the grid uses 1-based indexing for operations.

2. Change: Given an operation of the form C x y t, change the flower at cell ( (x, y) ) to type (t).

For example, if the grid is

[ \begin{bmatrix} 1 & 2 & 2 \ 3 & 1 & 1 \ 1 & 3 & 3 \end{bmatrix} ]

and the operations are

Q 1 1 (query), C 2 2 2 (change), Q 2 2 (query), C 3 3 2 (change), Q 2 2 (query),

the result of the queries would be 1, 3, 3 respectively. The DFS (Depth-First Search) technique is used to calculate the connected group sizes. Your task is to simulate these operations and output the results for each query.

inputFormat

The input is given via standard input (stdin) and is structured as follows:

• The first line contains two integers (n) and (m) (the number of rows and columns of the grid).
• The next (n) lines each contain (m) integers, representing the initial grid configuration. Each integer denotes the flower type in that cell.
• The following line contains an integer (k), the number of incompatible flower pairs.
• The next (k) lines each contain two integers representing an incompatible pair of flower types.
• The next line contains an integer (t), the number of operations.
• The following (t) lines each contain an operation in one of the following forms:
  • Q x y – Query the size of the connected component for the cell at row (x) and column (y).
  • C x y t – Change the flower at cell (x, y) to type (t).

Note: It is guaranteed that the provided coordinates use 1-based indexing.

outputFormat

For each query operation, output the size of the connected group (number of cells) that are connected to the queried cell and share the same flower type. Each result should be printed on a new line to standard output (stdout).## sample

3 3
1 2 2
3 1 1
1 3 3
2
1 2
1 3
5
Q 1 1
C 2 2 2
Q 2 2
C 3 3 2
Q 2 2

1
3
3