题目描述

Mirko 正在玩一款小游戏。在一个 $10$ 行 $n$ 列的矩阵中，他需要从左下角出发，避免在障碍物处停留，最终到达第 $n$ 列的任意位置。每秒，他都会向右移动一个单位。

在游戏中，Mirko 拥有一个喷气背包（游戏开始时关闭）：

• 打开喷气背包时，每秒他将额外向上移动一个单位（即向右上方移动），直到他处于矩阵顶端的一行。
• 关闭喷气背包时，每秒他将额外向下移动一个单位（即向右下方移动），直到他处于矩阵底端的一行。

他可以在任意一秒打开喷气背包，并在任意秒后关闭。将此记为一次操作。

现在，Mirko 想让你设计一系列操作，使他能够顺利结束游戏。

输入格式

第一行一个整数 $n$，表示矩阵的列数。

接下来 $10$ 行，每行 $n$ 个字符。表示相应位置是否存在障碍物。字符只可能是 . 或 X。

• . 表示该区域不存在障碍物。
• X 表示该区域存在障碍物。

输出格式

本题使用 Special Judge。

第一行一个非负整数 $p$，表示 Mirko 应进行操作的次数。

接下来 $p$ 行，每行两个正整数 $t_i$ 和 $x_i$，表示 Mirko 需要在第 $t_i$ 秒打开喷气背包，并在 $x_i$ 秒后关闭。

若存在多种答案，请输出任意一种。

另外：

• 操作应按时间顺序给出，且在一次操作完成前无法进行其他操作。即 $t_i+x_i\le t_{i+1}$。
• 游戏结束后 Mirko 无法进行任何操作。即 $t_i<n$。
• Mirko 不希望操作次数过多。即 $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 

提示

样例 1 解释

下图为样例输出一所表示的路径。

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

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$。

数据保证至少存在一种方案，能使得 Mirko 能够顺利结束游戏。

说明

题目译自 COCI2016-2017 CONTEST #1 T2 Jetpack。