High School Programming League Problems Archive

Adam lives in a house with a garden. In the garden he has a lawn and in the lawn he has grass that needs to be mowed. Adam likes cutting grass (he claims it's relaxing for him), but he has a small problem with his lawn mower, namely, it has some difficulties with turning.

The number of turns which have to be made while mowing does not only depend on the lawn itself but on the path of cutting, as well. That is why Adam has come up with an idea to optimise the path he will use to mow the lawn, subject to the following constraints:

• the lawn consists of squares, the length of whose sides is precisely equal to the size of the mower's blade,
• the mower can only be moved in four directions: up, down, left, and right (u, d, l, r),
• the problem of determining the path of cutting can be modeled by defining a sequence of moves which cover all of the squares of the lawn,
• the criterion for optimization is minimising the number of turns.

Adam has come up with an idea to define the best route and he would like you to compare your results with his. Whose method is going to be better?

Input

First, we are given the starting point (x, y) - and the mower is placed on (x, y) (x+1, y) (x+1, y+1) (x, y+1). we also have direction d – the initial orientation of the mower. Next, there is a description given of the border of the lawn which constists of: integer k – the number of line segments (4 <= k <= 1000), then there come the coordinates of the starting point (a, b) and k vectors [a_i, b_i] separated by commas, describing the i-th segment of the border when traversed in the clockwise direction (for each i, 1<= i <= k we have 0 < a_i² + b_i² < 10⁶ and a_ib_i=0).

Then there is given h - the number of "holes" in the lawn and then there are h descriptions of every hole (i.e., the coordinates of the starting point and of the outline, as above). A "hole" is a fragment of the terrain which does not require any mowing (bushes, flower beds, etc.).

You can asume that each outline is a closed line, in which no two segments cross, nonadjacent elements do not overlap, the total number of fields to be cut does not exceed 100000, and the whole of the lawn fits into a 1000x1000 square.

Output

First, output a single integer, describing the number of steps to make, followed by a string of letters describing the successive steps made while mowing. After all the steps have been completed, the mower should once again be located at the starting point. If the number of steps exceeds the 10*(number of lawn squares) your solution will be deemed incorrect. Likewise, your solution will be if at any time the lawn mower is located outside the lawn.

Scoring

For a single test, the score of your program is given as: max{0, r}, where r denotes the difference between the number of all lawn squares and the number of turns made during mowning, under the assumption that a turn by 180 degrees is considered as two turns. The total score of the program is the sum of points scored in all tests.

The number of points displayed in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example 1

Input:
(0, 0) u
4
(0, 0), [0, 2], [2, 0], [0, -2], [-2, 0]
0 
Output:
4
urdl

Scoring:
0

Example 2

Input:
(0, 0) d
6
(-5, -2), [0, 6], [7, 0], [0, -1], [-1, 0], [0, -5], [-6, 0]
2 
6 
(-3, 0), [0, 2], [1, 0], [0, -1], [1, 0], [0, -1], [-2, 0]
4 
(-1, 2), [0, 1], [1, 0], [0, -1], [-1, 0]

Output:
34
ddluuululldddrrdllluuuuurrrrrrlddd

Scoring:
19 

Please note that...

...submissions will be tested only during the last week of the series, will be visible to the submitting contestant only, and tested on the full set of test cases.

Please also note that...

On October 7 exemplary test cases have been revealed. Submissions will be tested using similar tests to those.

To be more precise there will be 5 test cases satisfying following conditions:

1. lawn with 12 elements of the border, no holes.
2. lawn with 4 elements of the border, 3 holes.
3. lawn irregularly shaped with several holes
4. lawn like a regular grid or a city plan with many holes.
5. lawn irregularly shaped with many holes.