Maze Polygon Reconstruction

Byteasar is fascinated by mazes. He has discovered that if you have a maze sketch in the plane in which all edges are parallel to the coordinate axes and every two consecutive edges are perpendicular, then placing the entrance on one of its walls allows one to traverse the entire maze returning to the entrance by keeping the right hand on the wall. During the traversal we note each turn: write L if a left turn is taken and P if a right turn is taken.

Given a word composed solely of the letters L and P (which is known to satisfy the necessary condition for such a polygon – namely that the total turning angle is \(\pm360^\circ\), or equivalently
\(90\times(\#L - \#P)=\pm360\)), your task is to construct a maze polygon whose boundary, drawn on grid paper, has all edges parallel to the axes and vertices with integer coordinates, and whose traversal (starting at some vertex and proceeding along the edges in order) produces the given sequence of turns.

Note: It is guaranteed that the input turn sequence is valid, i.e. there exists at least one solution. If there are several solutions, you may output any one of them.

Hint: A construction is possible since the turn sequence gives a system of two linear equations in the edge lengths. One simple approach is to assign positive integer lengths to all but two edges, and then solve for the remaining two. In some cases a small adjustment in one of the middle edges may be needed to get a positive solution.

All formulas are given in LaTeX format. For example, the total turning angle is given by:

\(\sum_{i=1}^{n} \theta_i = 90^\circ\times(\#L - \#P) = \pm360^\circ\).

inputFormat

The input consists of a single line containing a nonempty string S composed only of the characters L and P. The length of S is the number of turns in the polygon’s traversal. It is guaranteed that \(90\times(\#L - \#P)=\pm360\) so that a solution exists.

outputFormat

Output the polygon in the following format:

• The first line contains an integer n which is the number of vertices of the polygon.
• Each of the next n lines contains two space‐separated integers representing the x and y coordinates of the vertices in order (walking along the boundary). The first and last vertices are not repeated.

The polygon must be simple (non self-intersecting) and all edges must be axis–parallel.

sample

LLLL

4
0 0
1 0
1 1
0 1