Hot Spring Land Operations

You are given a grid representing a piece of land. Each cell in the grid is either a hot spring (1) or soil (0). Initially the grid configuration is provided. Then, two sets of operations are performed by XiaoD.

Operation 1 (Query):
XiaoD provides w query positions. For each query position, if the cell is a hot spring (1), its hot spring range is defined as the number of cells reachable (including itself) by moving in four directions (up, down, left, right) within cells that are hot springs. If the queried cell is soil (0), its range is 0. Among the given w positions (numbered 1,2,…,w in order of input), output the index of the position with the maximum range. If there is a tie, choose the one with the smallest index.

Operation 2 (Flip):
XiaoD then provides another w positions. For each given position, the terrain is flipped in sequence. That is, if the cell is soil (0), it is changed to a hot spring (1); if the cell is a hot spring (1), it is flipped to soil (0). However, when flipping a hot spring to soil, the move is only executed if doing so does not split the connected hot spring region.
Formally, if a cell currently is 1 and is adjacent (up, down, left, right) to one or more hot spring cells, then before flipping the cell you must check: if there are at most one adjacent hot spring cell, the flip is safe; if there are at least two, temporarily remove the cell (set it to 0) and perform a connectivity check among all its adjacent hot spring neighbors (using 4-directional moves). If they are all still mutually reachable, the flip is allowed; otherwise, the flip is cancelled (the cell remains 1).

After processing all the operations, output the result of the first query (i.e. the 1-indexed query position with maximum hot spring range) on the first line, followed by the final grid configuration (each row on a new line).

Note: All positions in the input are 1-indexed.

Formula note: When referring to the number of reachable cells, if a cell is a hot spring, then its reachable region size is determined by the connected component of cells
\(\{ (i,j) \mid grid[i][j]=1 \}\) containing that cell.

inputFormat

The input consists of the following parts:

1. The first line contains two integers n and m (1 \leq n, m \leq 500) representing the number of rows and columns of the grid.
2. The next n lines each contain a string of m characters. Each character is either 1 (hot spring) or 0 (soil).
3. A line containing an integer w (number of queries for operation 1).
4. w lines follow, each containing two integers r and c (1-indexed) — the row and column of a query position.
5. A line containing an integer w (number of flip operations for operation 2).
6. w lines follow, each containing two integers r and c (1-indexed) indicating the cell to flip.

outputFormat

Output the result of the query operation on the first line, i.e. the index (1-indexed and based on the given order) of the query position with the maximum hot spring range. Then, output n lines, each a string of m characters, representing the final grid configuration after processing all flip operations.

sample

3 3
111
101
111
3
2 2
1 1
3 3
3
2 1
2 3
1 2

2
111
001
111