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 " cm"$-by-$1 " cm"$ blocks, in any of the four cardinal directions to move a ball to a hole in the centre at $(0, 0)$. As shown in the figure, once the $1 " 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.
The input consists of:
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 on the next line, output $n$, the number of blocks to use. On each of the remaining $n$ lines, output $s$ and $t$, the integer coordinates of a block.
Otherwise, output "_impossible_".
You may use at most $n <= 10^4$ blocks. All coordinates used 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.
## Input
The input consists of: One line with a string $s$ consisting of only the characters "_LRUD_" ($1 <= | s | <= 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
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 on the next line, output $n$, the number of blocks to use. On each of the remaining $n$ lines, output $s$ and $t$, the integer coordinates of a block.Otherwise, output "_impossible_".You may use at most $n <= 10^4$ blocks. All coordinates used 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.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $, $ 3 \leq n \leq 2000 $, be the number of vertices of a simple polygon.
Let $ P = (v_1, v_2, \dots, v_n) $, where $ v_i = (x_i, y_i) \in \mathbb{R}^2 $, be the sequence of vertices in counter-clockwise order.
**Constraints**
The polygon is simple: vertices are distinct, and non-consecutive edges do not intersect or touch.
**Objective**
Find the minimum radius $ r \in \mathbb{R}_{\geq 0} $ such that the union of closed disks of radius $ r $ centered at each vertex $ v_i $ covers the entire polygonal region bounded by $ P $.
That is,
$$
\bigcup_{i=1}^n D(v_i, r) \supseteq \text{conv}(P)
$$
where $ D(v_i, r) = \{ p \in \mathbb{R}^2 \mid \|p - v_i\| \leq r \} $, and $ \text{conv}(P) $ denotes the polygonal region.
The minimal such $ r $ is the smallest value for which every point in the polygon lies within distance $ r $ of at least one vertex.