有一個無限大的二維棋盤，其中每個格子都有一個唯一的整數座標 $(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$$ 總分是移動軌跡中每個格子得分的總和。在此範例中，總分為 $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