Существует бесконечная двумерная шахматная доска, в которой каждая клетка имеет уникальные целочисленные координаты $(x, y)$. Начальная клетка имеет координаты $(0, 0)$. Если мы начнем с этой клетки, пройдем $x$ шагов вправо, а затем $y$ шагов вверх, мы окажемся в клетке $(x, y)$. Заметим, что $x$ и $y$ могут быть отрицательными, что означает движение в противоположном направлении.

Робот начинает движение из клетки $(0, 0)$ и выполняет последовательность команд $c_1 c_2 \dots c_n$, где каждая $c_i \in \{\text{L, R, D, U}\}$, что означает шаг в направлении влево, вправо, вниз и вверх соответственно. Например, если последовательность команд — LRLD, то пройденные клетки: $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$. Мы называем такую последовательность историей перемещений робота (в этом примере история содержит пять элементов).

Для каждой клетки $(x, y)$ в истории перемещений, если это $i$-й раз, когда робот посещает данную клетку, робот получает очки в размере $$f(x, y, i) = i \cdot ((|x| + 1) \oplus (|y| + 1)) + i$$ где $\oplus$ обозначает операцию побитового исключающего ИЛИ (xor).

Общий счет — это сумма очков за каждую клетку в истории перемещений. В данном примере общий счет равен $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$.

Для каждого $i$ от $1$ до $n$ ответьте на вопрос: если мы удалим $c_i$ из последовательности команд, каким будет общий счет, заработанный роботом после выполнения оставшейся последовательности $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$?

Входные данные

Первая строка содержит целое число $n$ ($2 \le n \le 3 \cdot 10^5$). Вторая строка содержит строку $c_1 c_2 \dots c_n$ длины $n$, обозначающую последовательность команд.

Выходные данные

Выведите $n$ строк. $i$-я строка должна содержать общий счет, если мы удалим команду $c_i$.

Примеры

Примеры 1

5
LRLDD

Выходные данные 1

14
11
14
16
16