522. Oil Wells

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

These are tough times for Berland nowadays. State property is being sold piece by piece, and even state oil company "BerOil" hasn't escaped the common lot.

A well-known entrepreneur Tapochkin decided to buy a piece of "BerOil"'s land. Tapochkin is very smart, so he wants to buy a piece of land that will contain all of the company's oil wells within its area or on its border. He has already bought a fence building machine that will move along the border of Tapochkin's new land and build a high fence! There is only one problem — the machine is defective.

Normally, the machine can move in any of the four directions: "north", "east", "south" and "west". Now, when it's broken, the situation is a bit different. Before the engine is turned on, the driver divides these four directions into two groups — two perpendicular directions in each group (e.g. "north" and "east" in one group, "south" and "west" in the other group). Then for some time the machine moves using only directions from the first group, after that — only directions from the second group. It's the driver who determines the moment of switching from one group to the other one.

The company's territory is split into equal squares by a system of roads. Half of the roads go in "north-south" direction, the other half — in "east-west" direction. The company has a vast territory that can be regarded as infinite. The roads form a square grid, each square of the grid has a side length equal to 1 km. Oil wells are located on the crossroads and their size is negligible, so they can be considered points.

Cartesian coordinate system can be applied to the company's territory, so that Ox axis is directed west-to-east, and Oy axis — south-to-north. Unit of length — 1 km. Initial position of the machine and coordinates of the oil wells are known. Find the area of the smallest possible piece of land that the machine can fence around, leaving all the oil wells inside the fenced area or on its border. Also, find the sequence of machine's movements. The border of Tapochkin's piece of land should be a closed non-degenerate polyline that doesn't cross or touch itself.

The first line of input contains three integers n, x0 and y0 (1 ≤ n ≤ 400, -400 ≤ x0,y0 ≤ 400), where n — amount of oil wells, (x0,y0) — initial position of the fence building machine. The following n lines contain coordinates of the wells xi, yi (-400 ≤ xi,yi ≤ 400). No two wells have identical coordinates.

Print the only number
to the output, if there is no solution. Otherwise print the area of Tapochkin's land in square kilometers to the first line, and the path of the fence building machine — to the second. The path of the machine is a sequence of characters "
", "
", "
" and "
", standing for movements one kilometer "west", "north", "east" or "south" correspondingly. You are allowed to print the path in any direction of driving — clockwise or counterclockwise, as it doesn't really change the closed polyline which the path represents. It there is more than one answer, you may print any of them.

sample input
sample output
3 4 2
5 6
7 2
9 4

sample input
sample output
2 1 -2
-1 2
1 -2

sample input
sample output
1 1 2
1 2

Online Contester Team © 2002 - 2010. All rights reserved.