무한히 큰 2차원 체스판이 있으며, 각 칸은 고유한 정수 좌표 $(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)$입니다. 이러한 순서를 로봇의 이동 경로(travel history)라고 부릅니다(이 예시에서 경로는 5개의 요소를 포함합니다).

이동 경로상의 모든 칸 $(x, y)$에 대하여, 이 칸을 로봇이 방문한 것이 $i$번째라면 로봇은 다음과 같은 점수를 얻습니다. $$f(x, y, i) = i \cdot ((|x| + 1) \oplus (|y| + 1)) + i$$ 총 점수는 이동 경로상의 모든 칸에서 얻은 점수의 합입니다. 이 예시에서 총 점수는 $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 \dots c_{i-1} c_{i+1} \dots c_n$을 수행한 후 얻게 되는 총 점수를 구하십시오.

입력

첫 번째 줄에는 정수 $n$ ($2 \le n \le 3 \cdot 10^5$)이 주어집니다. 두 번째 줄에는 명령 순서를 나타내는 길이 $n$의 문자열 $c_1 c_2 \dots c_n$이 주어집니다.

출력

$n$개의 줄을 출력하십시오. $i$번째 줄에는 $c_i$를 제거했을 때의 총 점수를 출력해야 합니다.

예제

입력 1

5
LRLDD

출력 1

14
11
14
16
16