These days, Tutu and Dandan have taken a liking to a new board game.

This game is played on an $n \times m$ grid. Before the game starts, one cell on the board is empty, and all other cells contain a piece, which is either black or white.

Each game always starts with Tutu making a move, after which both sides take turns. The specific moves are: In each of her turns, Tutu chooses a white piece adjacent to the empty cell and moves it into the empty cell. In each of his turns, Dandan chooses a black piece adjacent to the empty cell and moves it into the empty cell.

The first player unable to make a move according to the rules loses the game. For convenience, we denote the operation "move the piece in row $x$, column $y$ into the empty cell" as $M(x, y)$.

Examples of three games are shown below.

Figure 1

Figure 2

Figure 3

Recently, Tutu has been losing the game, and Dandan has been particularly arrogant. Tutu would like to ask her good friend—you—to help her. She has brought a record of a game she lost to Dandan; please point out all the places where she "made a mistake" in this game.

Note: Two cells are adjacent if and only if they share a common edge. Tutu's move is a "mistake" if and only if Tutu had a winning strategy before this move, but Dandan has a winning strategy after this move.

Input

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

The next $n$ lines describe the initial board. The $i$-th line contains $m$ characters, each being one of the uppercase letters "X", "O", or a dot ".", representing a black piece, a white piece, and an empty cell, respectively. The dot "." appears exactly once.

The next line contains an integer $k$ ($1 \le k \le 1000$), representing that Tutu and Dandan each made $k$ moves.

The next $2k$ lines describe the process of the game. The $(2i - 1)$-th line is Tutu's $i$-th move (operation numbered $i$), and the $2i$-th line is Dandan's $i$-th move. Each move is described by two integers $x, y$, representing moving the piece in row $x$, column $y$ into the empty cell.

The input guarantees that there is only one empty cell on the board, that every move made by Tutu and Dandan during the game is legal, and that Dandan eventually wins.

Output

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

The next $r$ lines give the operation numbers of the moves where Tutu "made a mistake" in increasing order. The $i$-th line contains an integer $a_i$, representing that Tutu's $i$-th mistake was her $a_i$-th move in the game.

Examples

Input 1

1 6
XO.OXO
1
1 2
1 1

Output 1

1
1

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

Output 2

0

Input 3

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

Output 3

2
1
2

Note

Example 1 corresponds to the game process in Figure 1. Example 2 corresponds to the game process in Figure 3.

Constraints

The range and characteristics of all test data are shown in the table below: