Existe un tablero de ajedrez bidimensional infinitamente grande, en el cual cada celda tiene una coordenada entera única $(x, y)$. La celda inicial tiene coordenadas $(0, 0)$. Si comenzamos desde esta celda, caminamos $x$ pasos a la derecha y luego caminamos $y$ pasos hacia arriba, llegaremos a la celda $(x, y)$. Tenga en cuenta que $x$ e $y$ pueden ser negativos, lo que significa caminar en la dirección opuesta.

Hay un robot que comienza en la celda $(0, 0)$ y luego ejecuta una secuencia de comandos $c_1 c_2 \dots c_n$, donde cada $c_i \in \{\text{L, R, D, U}\}$, lo que significa caminar un paso en la dirección Izquierda (Left), Derecha (Right), Abajo (Down) y Arriba (Up), respectivamente. Por ejemplo, si la secuencia de comandos es LRLD, entonces las celdas recorridas son $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$. Llamamos a dicha secuencia el historial de viaje del robot (en este ejemplo, el historial contiene cinco elementos).

Para cada celda $(x, y)$ en el historial de viaje, si es la $i$-ésima vez que el robot visita esta celda, entonces el robot obtiene una puntuación de $$f(x, y, i) = i \cdot ((|x| + 1) \oplus (|y| + 1)) + i.$$

La puntuación total es la suma de la puntuación de cada celda en el historial de viaje. En este ejemplo, la puntuación total es $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$.

Para cada $i$ desde 1 hasta $n$, por favor responda: si eliminamos $c_i$ de la secuencia de comandos, ¿cuál es la puntuación total obtenida por el robot después de ejecutar la secuencia restante $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$?

Entrada

La primera línea contiene un entero $n$ ($2 \le n \le 3 \cdot 10^5$). La segunda línea contiene una cadena $c_1 c_2 \dots c_n$ de longitud $n$, que denota la secuencia de comandos.

Salida

Imprima $n$ líneas. La $i$-ésima línea debe contener la puntuación total si eliminamos el comando $c_i$.

Ejemplos

Entrada 1

5
LRLDD

Salida 1

14
11
14
16
16