Simple Rectangle

A robot moves on a plane while drawing horizontal or vertical line segments. It starts at a given point, makes several moves, and finally returns to the starting point.

There are four possible directions: up, down, right, and left. They are written as U, D, R, and L. Every distance is a positive integer. For example, R 3 means moving 3 units to the right.

The complete trace of the robot may form several polygons. Among them, a rectangle whose interior contains no other point or line segment of the trace is called a simple rectangle. Find the simple rectangle with the smallest area among all simple rectangles formed by the given trace.

In the picture above, (4, 9) is the starting point, and the robot moves in the order R 7, D 5, L 10, U 3, and so on. The gray region is the simple rectangle with the smallest area, so it is the answer.

Whenever two segments meet, one is vertical and the other is horizontal, and they meet at a single point. Two horizontal segments never meet or overlap, and two vertical segments never meet or overlap.

The first line contains the starting point coordinates x and y, separated by a space.

The second line contains the number of moves n. The integer n is at most 100.

Each of the next n lines contains a direction (U, D, R, or L) and a distance, separated by a space. During the whole movement, both coordinates of the robot remain integers between 1 and 100, inclusive.

Print the coordinates of the lower-left corner of the smallest-area simple rectangle on the first line, and the coordinates of its upper-right corner on the second line.

Print each coordinate pair as x y. If there are multiple smallest-area simple rectangles, print any one of them.

If no simple rectangle exists, print 0 on the first line.