Problem Description

Log咕 Company consists of land divided into $n$ rows and $m$ columns, with the initial altitude of the land at the $i$-th row and $j$-th column being $a_{i,j}$. Both row and column numbers are indexed starting from 1.

Over a long period, a total of $T$ geographical changes occurred. Each change involves swapping the altitudes of two pieces of land.

A piece of land is considered a peak if its altitude is higher than that of all its directly adjacent lands (up, down, left, and right).

The leader of the Kingdom of Berland wants to know how many peaks there are in the kingdom after all geographical changes, and their respective coordinates.

For example, with $n=m=3$ and the following altitudes:

$$1 \ \ 2 \ \ 3 \\ 1 \ \ 4 \ \ 2\\ 1 \ \ 1 \ \ 2 $$

The peaks are located at $(1,3)$ and $(2,2)$.

Input Format

The first line of input contains two integers $n$ and $m$, representing the number of rows and columns, respectively.

The next $n$ lines, each containing $m$ integers, represent the altitudes $a_{i,j}$.

The next line contains a single integer $T$.

The next $T$ lines, each containing four integers $x_1, y_1, x_2, y_2$, represent the geographical changes where the land at row $x_1$ and column $y_1$ is swapped with the land at row $x_2$ and column $y_2$.

Output Format

The first line of output contains a single integer, representing the number of peaks $k$ after all geographical changes.

The next $k$ lines, each containing two integers $x$ and $y$, represent the coordinates of a peak at the $x$-th row and $y$-th column.

You can output the coordinates of the peaks in any order.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2
2 2
1 3

Input Sample #2

3 3
1 2 3
1 2 2
1 1 4
1
2 2 3 3

Output Sample #2

2
1 3
2 2

Notes

For $20\%$ of the data, $n=1$;
For another $20\%$ of the data, $m=1$;
For another $20\%$ of the data, $n=m$;
For another $20\%$ of the data, $T=0$;
For $100\%$ of the data,
$1 \le n,m \le 1000,
$0 \le T \le 10^5$,
$1 \le a_{i,j} \le 10^6$,
$1 \le x_1, x_2 \le n$,
1 \le y_1, y_2 \le m$.

见题面 Input 部分

见题面 Output 部分