Jetpack

Mirko got a new phone for his birthday. Like every kid these days he downloaded all the popular mobile games, one of which has the hero running with a jetpack on his back.

In that game the hero, Barry, runs across a field of 10 rows and $N$ columns of equal squares. Barry starts in the bottom left square and runs to the right at one square per second, and he has to avoid the obstacles in his way.

While Mirko holds the screen down, Barry turns on his jetpack and climbs one row per second. He keeps moving right at the same time, so he travels diagonally at 45 degrees. Once he reaches the top row he runs right along it until Mirko lets go. When Mirko releases the screen, Barry falls one row per second, and once he reaches the bottom row he runs right along that one.

Stated exactly: during second $t$, counting from 0, Barry moves from column $t$ to column $t+1$. If the screen is held during that second he also moves one row up, or stays in the top row if he is already there. If the screen is not held he moves one row down, or stays in the bottom row if he is already there. Every square Barry passes through must be free of obstacles.

Mirko started playing only recently and is still bad at it. Given the layout of the field, work out when he has to hold the screen so that Barry crosses all $N$ columns.

The first line contains the integer $N$, the width of the field ($1 \le N \le 10^5$).

Each of the next 10 lines contains $N$ characters, either X or .. An X is an obstacle and a . is a square Barry may pass through. The first of those lines is the top row of the field and the last one is the bottom row. Barry starts in the first square of the bottom row, and that square has no obstacle. Every input admits at least one way to finish the game.

Several schedules can work, so exactly one of them is required. Write a schedule as a string $b$ of length $N-1$ where, counting from 0, character $t$ of $b$ is 1 if the screen is held during second $t$ and 0 if it is not. Among all strings that let Barry finish, output the lexicographically smallest one. In other words, at every second release the screen whenever finishing the game is still possible afterwards.

Print the number of presses $P$ on the first line. Each of the next $P$ lines describes one press with two integers $t_i$ and $x_i$: Mirko presses the screen at second $t_i$ and holds it for $x_i$ seconds. These are the maximal blocks of consecutive 1 characters in $b$ listed in chronological order, so $t_i + x_i \le t_{i+1}$ and $t_i < N$. When $N = 1$, print a single line containing 0.