На двовимірній площині задані \(N\) точок. Початковими координатами \(i\)-ї точки є (\(x_i, y_i\)). Тепер кожна точка починає рухатися зі швидкістю 1 за секунду в напрямку, паралельному осі \(x\) або \(y\).

Вам надається символ \(d_i\), який задає конкретний напрямок, у якому рухається \(i\)-та точка, таким чином:

• Якщо \(d_i = R\), \(i\)-та точка рухається в додатному напрямку \(x\);

• Якщо \(d_i = L\), \(i\)-та точка рухається в від'ємному напрямку \(x\);

• Якщо \(d_i = U\), \(i\)-та точка рухається в додатному напрямку \(y\);

• Якщо \(d_i = D\), \(i\)-та точка рухається в від'ємному напрямку \(y\).

Ви можете зупинити всі точки в певний момент за вашим вибором після того, як вони почнуть рухатися (включаючи момент, коли вони починають рухатися).

Тоді нехай \(x_{max}\) і \(x_{min}\) є максимумом і мінімумом серед \(x\)-координат \(N\) точок відповідно.

Аналогічно, нехай \(y_{max}\) і \(y_{min}\) є максимумом і мінімумом серед координат \(y\) \(N\) точок відповідно.

Знайдіть мінімально можливе значення \((x_{max} - x_{min}) \times (y_{max} - y_{min})\).

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(1 \le N \le 10^5\)).

Наступні \(N\) рядків містять цілі числа \(x_i, y_i, d_i\) (\(-10^8 \le x_i,y_i \le 10^8\), \(d_i\) містить один із символів: \(U, D, L, R\). Числа та символ розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукане мінімальне значення \((x_{max} - x_{min}) \times (y_{max} - y_{min})\).

Результат буде оцінюватися з точністю до \(10^{-9}\).

Примітка

До прикладу 1:

Через три секунди дві точки зустрінуться в початку координат. Шуканим значенням на цей момент буде 0.

Приклад вхідних даних

2
0 3 D
3 0 L

Приклад вихідних даних

0

Приклад вхідних даних

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

Приклад вихідних даних

97.5

Приклад вхідних даних

20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D

Приклад вихідних даних

273