Les vaches construisent des formes avec $N$ ($1 \le N \le 25{,}000$) bottes cubiques $1\times1\times1$.

La botte 1 est au sol ; 2 à $N$ sont ajoutées successivement dans une position relative à une botte déjà posée. Exemple :

Botte 1 au sol.

Botte 2 à droite de 1.

Botte 3 devant 2.

Botte 4 devant 3.

Cela donne un L inversé :

                     +--+--+

                1-> /  /  /| <-2

                   +--+--+ +

                   | /  /|/

                   ++--+ +

                   /  /|/ <-3

                  +--+ +

                  |  |/ <-4

                  +--+

Ajoutons une botte :

Botte 5 au-dessus de botte 1.

La hauteur augmente :

                     +--+

                    /  /|

                   +--+ +--+

               5-> |  |/  /| <-2

                   +--+--+ +

               1-> | /  /|/

                   ++--+ +

                   /  /|/ <-3

                  +--+ +

                  |  |/ <-4

                  +--+

Mais ajouter cette instruction :

Botte 6 derrière botte 4.

Rend la forme invalide : 3 et 6 se superposent.

Pour $N$ bottes ainsi placées, affichez la surface exposée si valide. Une face exposée ne touche aucune face d’autre botte ni le sol (pas le dessous d’un cube au sol). Sinon $-1$. Aucune botte à plus de 25 largeurs de la première ni sous le sol.

Entrée

• Ligne 1 : entier $N$.

• Lignes $2..N$ : j X décrit bottes $2..N$, ligne 2 botte 2, ligne 3 botte 3, etc. X : L gauche, R droite, F devant, B derrière, O dessus, U dessous. Elles peuvent être collées et suspendues sans support inférieur.

Sortie

• Ligne 1 : surface exposée, sinon -1.

Exemples

Entrée 1

5
1 R
2 F
3 F
1 O

Sortie 1

18