National Olympiad in Informatics, China, 2011

Recently, Bunny and Eggy have developed an interest in a new type of board game.

This game is played on an ~n~ rows tall by ~m~ columns wide board. Once the game starts, the board contains a single square that is empty. All other squares contain a single piece that's either black or white.

Each game will always have Bunny go first, followed by them alternating. The general steps are:

• Every time Bunny moves, she will select a white piece adjacent to the empty square and move it onto the space.
• Every time Eggy moves, he will select a black piece adjacent to the empty square and move it onto the space.

The first person that cannot follow the above loses the game. To simplify our description, we denote the action of "moving the piece from row ~x~, column ~y~ to the empty space" as ~\mathrm M(x, y)~. The following are three examples of entire games.

Figure 1

Figure 2

Figure 3

Bunny has been losing a lot recently, and thus Eggy has been getting overly arrogant. Bunny wants to invite her good friend – you! – to help her. She has brought over a game which she has lost to Eggy, and wishes for you to point out all of the "mistakes" she made.

Note:

• Two squares are considered adjacent if and only if they share an edge.
• A move of Bunny's is a "mistake" if and only if Bunny had a guaranteed winning strategy before it was made, and Eggy had a guaranteed winning strategy after it was made.

Input Specification

The first line of input contains two positive integers ~n~ and ~m~.
The following ~n~ lines will describe the game board. The ~i^\text{th}~ of these lines contains ~m~ characters, where each character can either be an uppercase X, an uppercase O, or a period .. Respectively, they represent a black piece on a square, a white piece on a square, and an empty square. The . character will appear exactly once.
The following line contains a single integer ~k~ ~(1 \le k \le 1\,000)~, indicating that Bunny and Eggy each made ~k~ moves.
The following ~2k~ lines will describe the process of a game. The ~(2i-1)^\text{th}~ of these lines will represent Bunny's ~i^\text{th}~ move, and the ~(2i)^\text{th}~ of these lines will represent Eggy's ~i^\text{th}~ move. Each move will be described using two integers ~x~ and ~y~, indicating that the piece in row ~x~, column ~y~ will be moved onto the empty square.
The input guarantees that there will be exactly one empty square, all moves made by Bunny and Eggy in the process are valid, and that Eggy will be the winner at the end.

Output Specification

The first line of output should contain a single integer ~r~, representing the total number of times that Bunny has made a mistake.
The following ~r~ lines should give the actual move numbers of the mistakes in ascending order. The ~i^\text{th}~ of these lines should contain a single integer ~a_i~, indicating the ~i^\text{th}~ mistake Bunny made is her ~a_i^\text{th}~ move in the game.

Sample Input 1

1 6
XO.OXO
1
1 2
1 1

Sample Output 1

1
1

Explanation for Sample Output 1

This corresponds to the example in figure 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

Explanation for Sample Output 2

This corresponds to the example in figure 3.

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

Constraints

The attributes of all the test cases are outlined below.

Test Case	Range of ~n~	Range of ~m~
1	~n = 1~	~1 \le m \le 20~
2
3	~n = 3~	~m = 4~
4	~n = 4~	~m = 4~
5
6	~n = 4~	~m = 5~
7
8	~n = 3~	~m = 7~
9	~n = 2~	~1 \le m \le 40~
10
11
12
13
14
15	~1 \le n \le 16~	~1 \le m \le 16~
16
17	~1 \le n \le 40~	~1 \le m \le 40~
18
19
20

Problem translated to English by Alex.