Problem Description

There is a grid with $ H $ rows and $ W $ columns. Let the cell at the $ i $-th row from the top and the $ j $-th column from the left be called cell $(i,\ j)$.
A snake is located on this grid. The position of the snake is represented by a positive integer $ k $ and a sequence of $ k $ cell coordinates, $(x_1,\ y_1),\ (x_2,\ y_2),\ (x_3,\ y_3),\ \dots,\ (x_k,\ y_k)$, satisfying the following conditions:

• $1 \le x_i \le H$
• $1 \le y_i \le W$
• $(x_i,\ y_i) \neq (x_j,\ y_j)\ (i \neq j)$
• Cell $(x_i,\ y_i)$ and cell $(x_{i + 1},\ y_{i + 1})$ are adjacent and share an edge

You are given which cells on the grid are occupied by the snake. Specifically, if there exists an integer $i\ (1 \le i \le k)$ such that $(x_i,\ y_i) = (a,\ b)$, then $S_{a,\ b}$ is #; otherwise, it is ..
Find one possible $ k $ and the sequence $(x_1,\ y_1),\ (x_2,\ y_2),\ (x_3,\ y_3),\ \dots,\ (x_k,\ y_k)$.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $S_{1,\ 1}S_{1,\ 2}S_{1,\ 3}\ \dots\ S_{1,\ W}$ $S_{2,\ 1}S_{2,\ 2}S_{2,\ 3}\ \dots\ S_{2,\ W}$ $S_{3,\ 1}S_{3,\ 2}S_{3,\ 3}\ \dots\ S_{3,\ W}$ $\hspace{40pt}\ \vdots$ $S_{H,\ 1}S_{H,\ 2}S_{H,\ 3}\ \dots\ S_{H,\ W}$

Output Format

First, output $ k $ on the first line.
Then, from the second line to the $ k + 1 $-th line, output $ x_i $ and $ y_i $ in this order separated by a space on the $ 1 + i $-th line.
Any output that matches the situation described in the problem statement will be considered correct.

Sample Input and Output

Sample Input #1

3 3
##.
.##
###

Sample Output #1

7
1 1
1 2
2 2
2 3
3 3
3 2
3 1

Sample Input #2

3 4
####
####
.#..

Sample Output #2

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

Sample Input #3

3 3
.##
###
###

Sample Output #3

8
1 2
1 3
2 3
2 2
2 1
3 1
3 2
3 3

Notes/Hints

Note

Discussion of this problem is prohibited until 18:00 JST on December 27, 2020. If any discussion occurs, compensation may be claimed. It is okay to publish the total score and certification level after the exam, but please refrain from disseminating information about which problems were solved.

Constraints

• $1 \le H \le 4$
• $1 \le W \le 4$
• $S_{i,\ j}$ is either # or .
• There exists $ k $ and $(x_1,\ y_1),\ (x_2,\ y_2),\ (x_3,\ y_3),\ \dots,\ (x_k,\ y_k)$ that match the situation described in the problem statement

Sample Explanation 1

The reversed sequence is also considered correct.

Sample Explanation 2

There are several correct answers other than this and its reversed version.

见题面 Input 部分

见题面 Output 部分