{"raw_statement":[{"iden":"statement","content":"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.\n\nCarol 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.\n\nThe 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.\n\nDesign a board which can be won by applying her sequence of moves.\n\nThe input consists of: \n\nIf 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.\n\nOtherwise, output \"_impossible_\".\n\nYou 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.\n\n"},{"iden":"input","content":"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. "},{"iden":"output","content":"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."},{"iden":"examples","content":"InputDLDLRUR\nOutput-3 1\n8\n-1 -1\n-1 -2\n-2 1\n-3 -1\n-5 0\n-6 -1\n-7 -2\n-4 -3InputLRLRLRLRULD\nOutput1 1\n5\n2 1\n2 0\n-1 1\n-1 0\n-1 1000000000\nInputLRLR\nOutputimpossible\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 2000 $, be the number of vertices of a simple polygon.  \nLet $ 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.\n\n**Constraints**  \nThe polygon is simple: vertices are distinct, and non-consecutive edges do not intersect or touch.\n\n**Objective**  \nFind 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 $.  \nThat is,  \n$$\n\\bigcup_{i=1}^n D(v_i, r) \\supseteq \\text{conv}(P)\n$$  \nwhere $ D(v_i, r) = \\{ p \\in \\mathbb{R}^2 \\mid \\|p - v_i\\| \\leq r \\} $, and $ \\text{conv}(P) $ denotes the polygonal region.\n\nThe minimal such $ r $ is the smallest value for which every point in the polygon lies within distance $ r $ of at least one vertex.","simple_statement":"Find the smallest circle radius such that circles centered at each vertex of a given polygon (in counter-clockwise order) cover the entire polygon.","has_page_source":false}