In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Note: During the contest, you can ask for the score of three arbitrarily chosen submissions for this problem.
Byteasar read an interesting story recently. Its protagonist was some Greek crown prince who defeated a monster with a wool yarn, or something like that. But something else fascinated Byteasar about the story. What he liked most was the fact that the climax took place in a maze. From then on Byteasar is crazy about mazes.
Byteasar sketches mazes on a squared sheet of paper. Each sketch is a polygon with sides (representing the walls of the maze) parallel to either of the sheet's edges (i.e., the axes of the Carthesian coordinate system), and every two successive sides are perpendicular. Byteasar observed that if the entrance is placed on one of the sides of such a maze, then one can traverse the whole maze and return to the entrance by always keeping the right hand to the wall as one goes.
Moreover, throughout the maze traversal we can note the turns we take. We shall write the letter L if we turn left when we move along one wall to another, and P if we turn right in such case. Byteasar wonders for which words composed of the letters L and P there exists a maze whose traversal results in writing this very word.
The first line of the standard input gives a single -letter word () composed of the letters L and P, describing the sequence of successive turns made during the maze's traversal.
In tests worth 50% of the total points an additional constraint holds.
If no maze corresponds to the description given as input, then the word NIE (Polish for no) is to be printed on the standard output. Otherwise, exactly lines should be printed, specifying any maze (consistent with the input) as follows. The -th of these lines is to hold two integers, and (), separated by a single space, that are the coordinates of the -th vertex of the maze's sketch. The vertices are to be printed in their counterclockwise order on the polygon's perimeter; an arbitrary vertex can be chosen as the first one, and the position of the entrance need not be indicated.
For the input data:
the correct result is:
0 0 2 0 2 2 -1 2 -1 -2 1 -2 1 -1 0 -1
Sample grading tests:
For this problem, an output visualizer is provided that, given a file with a maze description in the output format, draws the maze itself. To run it, extract this archive and execute the command:
The visualizer's behavior for files that do not conform to the output format is undefined.
Task author: Tomasz Idziaszek<Submit a solution> [0/100]