Description

Note: During the contest, you may query the scores of any three submissions for this problem.

Bajtazar recently read an interesting story.

Its hero was a Greek prince who defeated a monster with a ball of thread, or something like that.

But what fascinated Bajtazar was that the climax took place in a maze.

Since then, Bajtazar has been very interested in mazes.

He sketches mazes on squared paper.

Each sketch is a polygon (representing the maze walls) whose edges are parallel to the edges of the paper (i.e., to the axes of the Cartesian coordinate system), and every two consecutive edges are perpendicular.

Bajtazar found that if the entrance is placed on some edge of the maze (not at a vertex), then by always walking with his right hand on the wall, one can traverse the entire maze and return to the entrance.

Moreover, during the traversal, we can record the directions of turns.

When moving from one wall to the next, if we turn left, we write the letter 'L'; if we turn right, we write the letter 'P'.

Bajtazar wants to know whether, for a given string consisting of letters 'L' and 'P', there exists a maze whose traversal produces exactly that string, and if so, output such a maze.

Input Format

The first line of the standard input contains a string $S$ consisting of letters 'L' and 'P' ($1 \leq |S| \leq 10^5$), describing the sequence of consecutive turns taken during the traversal of the maze.

In testcases worth 50% of the points, it additionally holds that $|S| \leq 1000$.

Output Format

If no maze corresponds to the input description, print the word 'NIE' (Polish for 'no') to the standard output.

Otherwise, print exactly $|S|$ lines, specifying any maze consistent with the input, in the following format:

On the $i$-th line, print two integers $x_i$ and $y_i$ (separated by a single space), which are the coordinates of the $i$-th vertex of the maze sketch. The vertices must be output in counterclockwise order along the outer boundary of the polygon; you may choose any vertex as the first one, and you do not need to indicate the entrance position.

LLLLPPLL

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

Hint

Translation by Deepseek-V3, with minor edits.

Translated by ChatGPT 5