Wall and Nails

There are N nails on one wall. Treat the wall as a two-dimensional plane and each nail as a point. No two different nails share the same x-coordinate or the same y-coordinate.

A rubber band is placed so that every remaining nail is inside it. The band forms the convex hull of the current set of nails. Until fewer than three nails remain, the following process is repeated.

1. Record the area of the polygon formed by the current rubber band.
2. Choose one of the current leftmost, rightmost, highest, or lowest nails.
3. Remove the chosen nail from the wall. The rubber band then surrounds all nails that remain.

For each step, the direction of the nail that is removed is given. Compute every recorded area.

The first line contains the number of nails N. (3 <= N <= 300000)

Each of the next N lines contains the coordinates x and y of one nail. Every coordinate is an integer between 1 and 1000000000, inclusive. No two different nails have the same x-coordinate or the same y-coordinate.

The last line contains a string of length N-2. Each character describes the nail to remove.

• L: the current leftmost nail
• R: the current rightmost nail
• U: the current highest nail
• D: the current lowest nail

Print the recorded areas in order, one per line. Each area must be printed with exactly one digit after the decimal point.