로봇

무한히 큰 2차원 체스판이 있고, 모든 칸은 정수 좌표 $(x, y)$로 나타낸다. 시작 칸의 좌표는 $(0, 0)$이다. 이 칸에서 오른쪽으로 $x$칸, 위쪽으로 $y$칸 이동하면 좌표가 $(x, y)$인 칸에 도착한다. $x$와 $y$는 음수일 수 있으며, 이는 반대 방향으로 이동함을 뜻한다.

$(0,0)$에서 출발하는 로봇이 명령열 $c_1 c_2 \ldots c_n$을 실행한다. 각 $c_i \in \{\mathtt{L}, \mathtt{R}, \mathtt{D}, \mathtt{U}\}$는 각각 왼쪽, 오른쪽, 아래, 위 방향으로 한 칸 이동하는 명령이다. 예를 들어 명령열이 $\mathtt{LRLD}$라면 로봇이 지나는 칸은 $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$이다. 이러한 열을 로봇의 이동 기록이라고 하며, 위 예에서 이동 기록은 다섯 개의 원소를 갖는다.

이동 기록에 있는 모든 칸 $(x, y)$에 대해, 로봇이 이 칸을 $i$번째로 방문할 때 얻는 점수는 $f(x, y, i) = i \cdot \left((|x| + 1) \mathrm{xor} (|y| + 1)\right) + i\text{.}$ 전체 점수는 이동 기록에 있는 모든 칸의 점수를 더한 값이다. 위 예에서 전체 점수는 $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$이다.

$1$ 이상 $n$ 이하의 모든 $i$에 대해 다음을 구하라. 명령열에서 $c_i$를 제거하고 남은 명령열 $c_1 c_2 \ldots c_{i - 1} c_{i + 1} \ldots c_n$을 실행했을 때 로봇이 얻는 전체 점수는 얼마인가?

첫째 줄에 정수 $n$이 주어진다. ($2 \le n \le 3 \cdot 10^{5}$)

둘째 줄에 길이가 $n$인 문자열 $c_1 c_2 \ldots c_n$이 주어지며, 이는 명령열을 나타낸다.

$n$개의 줄을 출력한다. $i$번째 줄에는 명령 $c_i$를 제거했을 때의 전체 점수를 출력한다.