Byteasar 最近读了一个有趣的故事。故事的主角是一位希腊王储，他用毛线团打败了怪物，诸如此类。但故事中还有其他东西让 Byteasar 着迷。他最喜欢的是故事的高潮发生在迷宫中。从那时起，Byteasar 就对迷宫着了迷。

Byteasar 在方格纸上绘制迷宫。每个草图都是一个多边形，其边（代表迷宫的墙壁）平行于纸张的边缘（即笛卡尔坐标系的轴），且每两条相邻的边都相互垂直。Byteasar 观察到，如果将入口放置在迷宫的一条边上，那么人们可以通过始终保持右手贴墙行走来遍历整个迷宫并回到入口。

此外，在遍历迷宫的过程中，我们可以记录下所做的转弯。如果我们沿着一面墙走到另一面墙时向左转，就记为字母 L；如果向右转，则记为 P。Byteasar 想知道，对于哪些由字母 L 和 P 组成的单词，存在一个迷宫，其遍历过程产生的记录恰好就是这个单词。

输入格式

标准输入的第一行给出一个由字母 L 和 P 组成的 $n$ 个字母的单词（$1 \le n \le 100,000$），描述了遍历迷宫时连续转弯的序列。

在总分 $50\%$ 的测试点中，满足额外约束 $n \le 2500$。

输出格式

如果没有迷宫符合给定的输入描述，则在标准输出上打印单词 NIE（波兰语中的“不”）。否则，应打印恰好 $n$ 行，指定一个符合输入的迷宫，格式如下：第 $i$ 行包含两个整数 $x_{i}$ 和 $y_{i}$（$-10^{9} \le x_{i}, y_{i} \le 10^{9}$），由单个空格分隔，表示迷宫草图的第 $i$ 个顶点的坐标。顶点应按多边形周长的逆时针顺序打印；可以任意选择一个顶点作为第一个顶点，无需标注入口位置。

样例

输入 1

LLLLPPLL

输出 1

0 0
2 0
2 2
-1 2
-1 -2
1 -2
1 -1
0 -1

说明

• 1ocen: $n=12$，单词为 LLLLLLLLLLLL，答案为 NIE；
• 2ocen: $n=100$，左手螺旋；
• 3ocen: $n=100,000$，楼梯状。

输出可视化

对于此问题，提供了一个输出可视化工具，给定一个符合输出格式的迷宫描述文件，它会绘制出迷宫本身。要运行它，请解压此归档文件并执行以下命令：

./labwiz

对于不符合输出格式的文件，可视化工具的行为是未定义的。