Mucche costruiscono figure con $N$ ($1 \le N \le 25{,}000$) balle cubiche $1\times1\times1$.

Balla 1 al suolo; 2 fino a $N$ aggiunte in sequenza relativamente a una già posta. Esempio:

Balla 1 al suolo.

Balla 2 a destra di 1.

Balla 3 davanti a 2.

Balla 4 davanti a 3.

Forma L invertita:

                     +--+--+

                1-> /  /  /| <-2

                   +--+--+ +

                   | /  /|/

                   ++--+ +

                   /  /|/ <-3

                  +--+ +

                  |  |/ <-4

                  +--+

Aggiungere balla:

Balla 5 sopra balla 1.

Aumenta altezza:

                     +--+

                    /  /|

                   +--+ +--+

               5-> |  |/  /| <-2

                   +--+--+ +

               1-> | /  /|/

                   ++--+ +

                   /  /|/ <-3

                  +--+ +

                  |  |/ <-4

                  +--+

Ma altra istruzione:

Balla 6 dietro balla 4.

Figura invalida: 3 e 6 si sovrappongono.

Date $N$ balle e posizioni, stampa superficie esposta se valida. Faccia esposta non tocca facce di altre balle né suolo (non base di cubo al suolo). Invalida $-1$. Nessuna oltre 25 larghezze dalla prima né sotto suolo.

Input

• Riga 1: intero $N$.

• Righe $2..N$: j X per balle $2..N$, riga 2 balla 2, riga 3 balla 3 ecc. X: L sinistra, R destra, F davanti, B dietro, O sopra, U sotto. Si possono incollare e sospendere senza sostegno inferiore.

Output

• Riga 1: superficie esposta o -1 invalida.

Esempi

Input 1

5
1 R
2 F
3 F
1 O

Output 1

18