P6285 [COCI 2016/2017 #1] Jetpack

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

#### 样例 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T2 Jetpack_**。