Problem Description

Carol enjoys playing with wooden games. The objective of the game that fascinates her the most is to tilt a maze, made out of $1\text{ cm}$-by-$1\text{ cm}$ blocks, in any of the four cardinal directions to move a ball to a hole in the centre at $(0,0)$. Once the $1\text{ cm}$ wide ball starts moving, it keeps going until either it runs into a wooden block, or it falls into the hole---whichever comes first.

Carol is interested in designing a maze of her own, and like any good game designer she already has a fixed solution in mind. This is given as a sequence of tilt moves which must all be followed in order. If any move causes nothing to happen, for example because the ball is up against a block in that direction or already in the hole, the solution does not count.

The ball can be placed anywhere to start. Carol will take care of adding a square border of blocks covering the rows and columns $10^9+1$ cells away from the centre in each direction.

Design a board which can be won by applying her sequence of moves.

:::align{center}

:::

Input Format

The input consists of:

• One line with a string $s$ consisting only of the characters LRUD ($1\le |s|\le 20$), the sequence of moves. These characters correspond to the directions $-x,+x,+y,-y$ respectively. No two consecutive characters in $s$ are the same.

Output Format

If it is possible to create a maze with the given solution, first output $x$ and $y$, the integer coordinates for the ball to start at. Then output $n$, the number of blocks to use, followed by $n$ lines containing the integer coordinates of the blocks.

Otherwise, output impossible. You may use at most $10^4$ blocks. All coordinates must be at most $10^9$ in absolute value. No coordinate pair may be the same as the centre or any other coordinate pair. If there are multiple valid solutions, you may output any one of them.

DLDLRUR

-3 1
8
-1 -1
-1 -2
-2 1
-3 -1
-5 0
-6 -1
-7 -2
-4 -3

LRLRLRLRULD

1 1
5
2 1
2 0
-1 1
-1 0
-1 1000000000

LRLR

impossible