P16990 [NWERC 2018] 游戏设计 / Game Design

译自 [NWERC 2018](https://2018.nwerc.eu/) G 题。

Carol 喜欢玩木制游戏。她最着迷的游戏目标是倾斜一个由 $1\text{ cm}\times 1\text{ cm}$ 木块组成的迷宫，使一个球通过四个基本方向的倾斜移动到中心 $(0,0)$ 处的洞中。如下图所示，一旦这个 $1\text{ cm}$ 宽的球开始移动，它会一直前进，直到撞到木块，或者掉进洞里——两者中先发生的为准。 Carol 想设计一个自己的迷宫。和任何优秀的游戏设计师一样，她已经有一个固定的解法序列。这个解法给出为一串必须按顺序执行的倾斜操作。如果某次操作没有造成任何移动，例如球正好贴着该方向的木块，或者已经在洞里，那么这个解法就不算有效。 球的初始位置可以任意选择。Carol 会负责在距离中心 $10^9+1$ 个格子的行和列处加上一圈方形边界木块。 请你设计一个棋盘，使得按照她给出的操作序列可以获胜。 :::align{center}  :::

输入包括： - 一行一个只包含字符 `LRUD` 的字符串 $s$（$1\le |s|\le 20$），表示操作序列。这些字符分别对应方向 $-x,+x,+y,-y$。字符串 $s$ 中没有两个相邻字符相同。

如果可以构造出一个具有给定解法的迷宫，首先输出整数坐标 $x$ 和 $y$，表示球的初始位置。然后下一行输出 $n$，表示使用的木块数量。接下来的 $n$ 行中，每行输出两个整数 $s,t$，表示一个木块的坐标。 否则，输出 `impossible`。 你最多可以使用 $n\le 10^4$ 个木块。所有使用到的坐标绝对值都不得超过 $10^9$。任何坐标对都不能与中心或其他坐标对相同。如果存在多种合法方案，你可以输出任意一种。

【数据规模与约定】 具体限制见输入格式。