Description

Mirko is playing a small game. In a $10$-row, $n$-column grid, he needs to start from the bottom-left corner, avoid landing on obstacles, and finally reach any position in column $n$. Each second, he moves one unit to the right.

In the game, Mirko has a jetpack (turned off at the start):

• When the jetpack is turned on, each second he additionally moves one unit upward (i.e. he moves up-right), until he reaches the top row of the grid.
• When the jetpack is turned off, each second he additionally moves one unit downward (i.e. he moves down-right), until he reaches the bottom row of the grid.

He may turn on the jetpack at any second, and turn it off after any number of seconds. This is considered one operation.

Now, Mirko wants you to design a sequence of operations so that he can finish the game successfully.

Input Format

The first line contains an integer $n$, the number of columns of the grid.

The next $10$ lines each contain $n$ characters, describing whether there is an obstacle at each position. Each character is either . or X.

• . means there is no obstacle in that cell.
• X means there is an obstacle in that cell.

Output Format

This problem uses Special Judge.

The first line contains a non-negative integer $p$, the number of operations Mirko should perform.

The next $p$ lines each contain two positive integers $t_i$ and $x_i$, meaning that Mirko should turn on the jetpack at second $t_i$ and turn it off after $x_i$ seconds.

If multiple answers exist, output any one of them.

Additionally:

• Operations must be given in chronological order, and no other operation may be performed before the current one finishes, i.e. $t_i+x_i\le t_{i+1}$.
• After the game ends, Mirko cannot perform any operations, i.e. $t_i<n$.
• Mirko does not want too many operations, i.e. $0\le p\le 5\times 10^4$.

11
.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
...........
.....X.....
....XX...X.
...XX...XX.
...X...XX.. 

2
1 4
7 2 

20
X..................X
.X................X.
..X..............X..
...X............X...
....X..........X....
.....X........X.....
......X......X......
.......X....X.......
........X..X........
.........XX......... 

1
8 10 

Hint

Explanation of Sample 1

The figure below shows the path represented by the sample output.

.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
.....*...*.
....*X*.*.*
...*XX.*.X.
..*XX...XX.
**.X...XX.. 

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^5$.

The testdata guarantees that at least one solution exists that allows Mirko to finish the game successfully.

Notes

Translated from COCI2016-2017 CONTEST #1 T2 Jetpack。

Translated by ChatGPT 5