Il existe un échiquier bidimensionnel infiniment grand, dans lequel chaque case possède une coordonnée entière unique $(x, y)$. La case de départ a pour coordonnée $(0, 0)$. Si nous partons de cette case, marchons $x$ pas vers la droite, puis marchons $y$ pas vers le haut, nous arriverons à la case $(x, y)$. Notez que $x$ et $y$ peuvent être négatifs, ce qui signifie marcher dans la direction opposée.

Il y a un robot qui commence à la case $(0, 0)$ puis exécute une séquence de commandes $c_1 c_2 \dots c_n$, où chaque $c_i \in \{\text{L, R, D, U}\}$, signifiant marcher d'un pas dans la direction Gauche (Left), Droite (Right), Bas (Down), Haut (Up), respectivement. Par exemple, si la séquence de commandes est LRLD, alors les cases parcourues sont $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$. Nous appelons cette séquence l'historique de déplacement du robot (dans cet exemple, l'historique contient cinq éléments).

Pour chaque case $(x, y)$ dans l'historique de déplacement, s'il s'agit de la $i$-ième fois que le robot visite cette case, alors le robot gagne un score de $$f(x, y, i) = i \cdot ((|x| + 1) \oplus (|y| + 1)) + i.$$ Le score total est la somme du score de chaque case dans l'historique de déplacement. Dans cet exemple, le score total est $f(0, 0, 1) + f(-1, 0, 1) + f(0, 0, 2) + f(-1, 0, 2) + f(-1, -1, 1) = 1 + 4 + 2 + 8 + 1 = 16$.

Pour chaque $i$ de $1$ à $n$, veuillez répondre : si nous supprimons $c_i$ de la séquence de commandes, quel est le score total gagné par le robot après avoir exécuté la séquence restante $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$ ?

Entrée

La première ligne contient un entier $n$ ($2 \le n \le 3 \cdot 10^5$). La deuxième ligne contient une chaîne $c_1 c_2 \dots c_n$ de longueur $n$, désignant la séquence de commandes.

Sortie

Affichez $n$ lignes. La $i$-ième ligne doit contenir le score total si nous supprimons la commande $c_i$.

Exemples

Entrée 1

5
LRLDD

Sortie 1

14
11
14
16
16