Avioane

Cerință

Se dau $n$ perechi de coordonate care reprezintă pozițiile inițiale a $n$ avioane. Fiecare avion $i$ are și o direcție de zbor $d_i$. Aceasta poate fi 'U' (sus), 'D' (jos), 'L' (stânga) sau 'R' (dreapta). La secunda $0$, avioanele vor începe să zboare în direcția dată cu o viteză constantă de o unitate pe secundă.

Când două avioane se află la același coordonate, acestea nu se ciocnesc, ci își continuă zborul, fiind la altitudini diferite. Determinați numărul de perechi $(i,j)$ ($1\le i<j\le n$) pentru care avioanele $i$ și $j$ vor avea, la un anumit moment de timp, aceleași coordonate.

Date de intrare

Pe prima linie se vor afla valorile $n$ (numărul de avioane). Pe a $i$-a din următoarele $n$ linii se vor afla valorile $x_i$ și $y_i$ (coordonatele de start ale avionului $i$), cât și caracterul $d_i$ (reprezentând direcția de start).

Date de ieșire

Pe prima linie se va afișa un singur număr, reprezentând numărul de perechi de avioane $(i,j)$ care se vor afla vreodată la aceleași coordonate. Se recomandă folosirea tipului de date long long.

Restricții și precizări

Pentru toate testele, se respectă $1 \le n \le 5\cdot10^5$ și $1\le x_i,y_i\le 10^6$ pentru orice $1\le i\le n$. De asemenea, oricare două avioane se află la poziții distincte.

Exemplul 1

stdin

4
1 2 D
2 1 R
2 4 L
3 4 L

stdout

3

Explicație

Exemplul este ilustrat în imaginea de mai sus. Liniile punctate reprezintă traseul avioanelor, iar locurile unde perechile de avioane se întâlnesc sunt încercuite.

Exemplul 2

stdin

2
1 3 D
2 1 R

stdout

0

Explicație

Nu este de ajuns ca traseele a două avioane să se intersecteze. Acestea trebuie să se afle în locul de intersecție în același timp.

Exemplul 3

stdin

3
1 2 D
2 1 R 
3 2 U

stdout

3

Explicație

Oricare două avioane se vor întâlni la aceleași coordonate $(2, 2)$. Chiar dacă coordonatele de întâlnire vor fi aceleași pentru cele $3$ perechi, acestea se numără separat.