Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Tí vào nhà kho phát hiện ra chiếc bàn cờ cũ của mình, nhưng không hiểu sao đã bị ai phá hỏng, N chiếc đinh đã bị đóng lên trên bàn cờ. Bàn cờ được đánh dấu theo hệ tọa độ Oxy. Tí nghĩ ra một trò khá thú vị.

Tí đã lấy trộm dây buộc tóc của em gái, rồi để chiếc dây chun bọc kín tất cả các chiếc đinh. Theo bản chất đàn hồi tự nhiên, chiếc dây sẽ tự co lại, và nó chiếm giữ đa giác lồi lớn nhất tạo bởi các chiếc đinh.

Tí thực hiện lần lượt các thao tác sau, cho đến khi còn lại 3 chiếc đinh trên bàn cờ.

1. Viết ra diện tích mà chiếc dây chiếm giữ.

2. Chọn ra 1 chiếc đinh ở ngoài cùng bên trái, bên phải, bên trên hoặc bên dưới.

3. Nhổ đi chiếc đinh đã lựa chọn. Do đó, chiếc dây sẽ tự đàn hồi và co lại về vị trí mới.

Cho biết trước chuỗi sự lựa chọn các chiếc đinh của Tí, nhiệm vụ của bạn là tính toán diện tích mà chiếc dây buộc tóc chiếm giữ tại mỗi bước.

Input

Dòng đầu tiên là số nguyên N (3 ≤ N ≤ 300 000), là số chiếc đinh trên bàn cờ.

N dòng tiếp theo, mỗi dòng gồm 2 số nguyên x_i, y_i (1 <= x_i, y_i <= 1 000 000 000) là tọa độ của chiếc đinh thứ i. Không có 2 chiếc đinh nào có cùng hoành độ hoặc tung độ.

Dòng tiếp theo là mỗi chuỗi các kí tự 'L', 'R', 'U' và 'D' có độ dài N – 2. Các chữ cái đại diện cho:

· 'L' cho chiếc đinh ở ngoài cùng bên trái (hoành độ x nhỏ nhất),

· 'R' cho chiếc đinh ở ngoài cùng bên phải (hoành độ x lớn nhất),

· 'U' cho chiếc đinh ở trên cùng (tung độ y lớn nhất),

· 'D' cho chiếc đinh ở dưới cùng (tung độ y nhỏ nhất).

Output

In ra N-2 số, mỗi số trên một dòng. Mỗi số lần lượt là diện tích mà Tí đã ghi chép lại, độ chính xác là 1 chữ số sau dấu thập phân.

Example

Test 1:

Input:

5
1 4
2 2
4 1
3 5
5 3
LUR

Output:

9.0
6.5
2.5

Test 2:

Input:

8
1 6
2 4
3 1
4 2
5 7
6 5
7 9
8 3
URDLUU

Output:

34.0
24.0
16.5
14.0
9.5
5.0

Giải thích test 2: