Mirko's Jetpack Challenge

Mirko is playing a game on a grid with 10 rows and n columns. He starts at the bottom‐left cell (row 10, column 1) and his goal is to reach any cell in column n without ever landing on an obstacle.

At every second Mirko automatically moves one cell to the right. In addition, he has a jetpack which can be toggled on or off. Initially the jetpack is off. The rules for vertical movement are as follows:

• When the jetpack is off, at each second he moves one cell downward if he is not already at the bottom row; otherwise, he stays in the bottom row. In other words, if his current row is r, then his new row is \[ r' = \begin{cases} r+1 & \text{if } r<10, \\ r & \text{if } r = 10. \end{cases} \]
• When the jetpack is on, at each second he moves one cell upward if he is not already at the top row; otherwise, he stays in the top row. That is, his new row is \[ r' = \begin{cases} r-1 & \text{if } r>1, \\ r & \text{if } r = 1. \end{cases} \]

Mirko may, at the beginning of any second, choose to toggle the state of the jetpack. An operation is defined as turning the jetpack on (when it is off) and, at a later second, turning it off (when it is on). When no toggling is performed, he continues in the current state. Note: Mirko must finish the game with the jetpack off (i.e. all operations must be complete).

The grid contains obstacles. The input grid is given as 10 lines of characters for n columns; each character is either . (an empty cell) or # (an obstacle). The first input row corresponds to the top row (row 1) and the tenth row corresponds to the bottom row (row 10). The starting cell (row 10, column 1) is guaranteed to be obstacle‐free. At every move the cell where Mirko lands must not contain an obstacle.

Your task is to compute a valid sequence of operations (if one exists) that allows Mirko to complete the game successfully. If no valid sequence exists, output IMPOSSIBLE. Otherwise, output the number of operations followed by the operations in the order they occur. Each operation is represented by two integers: the second (or move number) at which Mirko turns his jetpack on and the second at which he turns it off. The move number corresponds to the time when moving from column j to column j+1 (with the starting column being 1 and the game lasting n-1 moves).

inputFormat

The first line contains a single integer n (the number of columns).
The next 10 lines each contain a string of exactly n characters, representing the grid. The characters are either . (empty cell) or # (obstacle). The first line corresponds to row 1 (top) and the tenth line to row 10 (bottom).

outputFormat

If a valid sequence of operations exists, output the number of operations k on the first line. Then output k lines, each containing two space‐separated integers representing the move numbers at which Mirko toggles his jetpack on and subsequently off. If there is no valid sequence, output a single line containing IMPOSSIBLE.

sample

5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

0