Istnieje nieskończenie wielka dwuwymiarowa szachownica, w której każda komórka ma unikalne współrzędne całkowite $(x, y)$. Komórka startowa ma współrzędne $(0, 0)$. Jeśli zaczniemy od tej komórki, przejdziemy $x$ kroków w prawo, a następnie $y$ kroków w górę, dotrzemy do komórki $(x, y)$. Zauważ, że $x$ oraz $y$ mogą być ujemne, co oznacza poruszanie się w przeciwnym kierunku.

Robot zaczyna w komórce $(0, 0)$, a następnie wykonuje sekwencję poleceń $c_1 c_2 \dots c_n$, gdzie każde $c_i \in \{\text{L, R, D, U}\}$, co oznacza wykonanie jednego kroku odpowiednio w lewo, prawo, dół lub górę. Na przykład, jeśli sekwencja poleceń to LRLD, to odwiedzone komórki to $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$. Taką sekwencję nazywamy historią podróży robota (w tym przykładzie historia zawiera pięć elementów).

Dla każdej komórki $(x, y)$ w historii podróży, jeśli jest to $i$-ta wizyta robota w tej komórce, robot otrzymuje wynik: $$f(x, y, i) = i \cdot (|x| + 1) \oplus (|y| + 1) + i$$ gdzie $\oplus$ oznacza operację XOR.

Całkowity wynik to suma wyników dla każdej komórki w historii podróży. W tym przykładzie całkowity wynik wynosi $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$.

Dla każdego $i$ od $1$ do $n$, odpowiedz na pytanie: jeśli usuniemy $c_i$ z sekwencji poleceń, jaki będzie całkowity wynik uzyskany przez robota po wykonaniu pozostałej sekwencji $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$?

Wejście

Pierwsza linia zawiera liczbę całkowitą $n$ ($2 \le n \le 3 \cdot 10^5$). Druga linia zawiera ciąg znaków $c_1 c_2 \dots c_n$ o długości $n$, oznaczający sekwencję poleceń.

Wyjście

Wypisz $n$ linii. $i$-ta linia musi zawierać całkowity wynik po usunięciu polecenia $c_i$.

Przykład

Wejście 1

5
LRLDD

Wyjście 1

14
11
14
16
16