题目描述

题目译自 XX Olimpiada Informatyczna — III etap Labirynt

Bajtazar 最近读了一本引人入胜的故事，主角是一位希腊王子，凭借一团毛线击败了可怕的怪兽——诸如此类的传奇。不过，最让他着迷的不是这些，而是故事中关键场景发生在一个迷宫里。从此，他对迷宫着了迷。

Bajtazar 在方格纸上绘制迷宫平面图。每个平面图是一个多边形，其边（代表迷宫墙壁）与纸张边缘平行（即平行于直角坐标系的轴），且相邻两条边相互垂直。他发现，若在迷宫某堵墙上设置入口，进入后始终右手扶墙行走，必定能绕迷宫一周，最终回到入口。

更妙的是，在绕行时可以记录转弯情况：若转到下一堵墙时向左转，记为 L；向右转，记为 P。Bajtazar 想知道，对于一个由 L 和 P 组成的字符串，是否存在一个迷宫，使得绕行时会记录下这个字符串。

输入格式

第一行包含一个长度为 $n$ $(1 \leq n \leq 100000)$ 的字符串，由字母 L 和 P 组成，描述绕行迷宫时遇到的连续转弯序列。

输出格式

若无法根据输入描述构造迷宫，输出 NIE。

否则，输出 $n$ 行，描述一个迷宫。第 $i$ 行包含两个整数 $x_i, y_i$ $(-10^9 \leq x_i, y_i \leq 10^9)$，表示迷宫平面图上第 $i$ 个顶点的坐标。顶点需按多边形周界的逆时针顺序输出，可从任意顶点开始，无需标注入门位置。

LLLLPPLL

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

附加样例

1. $n=12$，字符串为 LLLLLLLLLLLL，答案为 NIE。
2. $n=100$，向左旋转的螺旋。
3. $n=100000$，阶梯状迷宫。

数据范围与提示

对于 $50\%$ 的测试数据，$n \leq 2500$。