Problem Description

Recently, Rabbit and Egg have become fond of a new board game.

The game is played on a board with $n$ rows and $m$ columns. Before the game starts, one cell on the board is empty, and the other cells contain either a black or a white piece.

Rabbit always starts the game, and then they take turns making moves. The rules for each move are as follows:

• Rabbit chooses a white piece adjacent to the empty cell and moves it into the empty cell.
• Egg chooses a black piece adjacent to the empty cell and moves it into the empty cell.

The person who cannot make a valid move loses the game. For convenience, the move "move the piece in the $x$-th row and $y$-th column into the empty cell" is denoted as $M(x,y)$.

Here are examples of three games:

Rabbit has been losing frequently, and Egg has been particularly boastful. Therefore, Rabbit wants her friend, you, to help her. She has brought a recorded game where she lost to Egg, and she wants you to identify all the "mistakes" she made in that game.

Note:

• Two cells are adjacent if and only if they share a common edge.
• A move by Rabbit is considered a "mistake" if, before this move, Rabbit had a winning strategy, but after this move, Egg has a winning strategy.

Input Format

The first line of input contains two positive integers $n$ and $m$.

The next $n$ lines describe the initial board. Each line contains $m$ characters, which can be either uppercase letter X, uppercase letter O, or a dot ., representing a black piece, a white piece, or an empty cell, respectively. The dot . appears exactly once.

The next line contains an integer $k$ ($1 \leq k \leq 1000$), indicating that Rabbit and Egg each made $k$ moves.

The next $2k$ lines describe the sequence of moves in the game. The $(2i - 1)$-th line is Rabbit's $i$-th move (numbered as $i$), and the $2i$-th line is Egg's $i$-th move. Each move is described by two integers $x$ and $y$, representing the move $M(x,y)$.

The input guarantees that there is exactly one empty cell on the board, and all moves made by Rabbit and Egg are valid, with Egg winning the game.

Output Format

The first line of the output contains an integer $r$, representing the total number of mistakes Rabbit made.

The next $r$ lines contain the numbers of the moves where Rabbit made mistakes, in increasing order. Each line contains an integer $a_i$, indicating that Rabbit's $i$-th mistake was her $a_i$-th move in the game.

Sample Input and Output

Sample Input #1

1 6 
XO.OXO 
1 
1 2 
1 1 

Sample Output #1

1
1

Sample Input #2

3 3 
XOX 
O.O 
XOX 
4 
2 3 
1 3 
1 2 
1 1 
2 1 
3 1 
3 2 
3 3 

Sample Output #2

0

Sample Input #3

4 4 
OOXX 
OXXO 
OO.O 
XXXO 
2 
3 2 
2 2 
1 2 
1 3 

Sample Output #3

2
1
2

Notes/Hints

For $100\%$ of the data, $1 \leq n \leq 40$, $1 \leq m \leq 40$, $1 \leq k \leq 1000$.

见题面 Input 部分

见题面 Output 部分