無限に広がる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}\}$ は、それぞれ左、右、下、上に1ステップ歩くことを意味します。例えば、コマンドの列が LRLD である場合、移動するマスは $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$ となります。この列をロボットの移動履歴と呼びます（この例では、履歴には5つの要素が含まれます）。

移動履歴に含まれるすべてのマス $(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$ となります。

$1$ から $n$ までのすべての $i$ について、コマンドの列から $c_i$ を取り除いた場合、残りのコマンド列 $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$ を実行した後にロボットが獲得する合計スコアを答えてください。

入力

1行目には整数 $n$ ($2 \le n \le 3 \cdot 10^5$) が与えられます。 2行目には長さ $n$ の文字列 $c_1 c_2 \dots c_n$ が与えられ、コマンドの列を表します。

出力

$n$ 行出力してください。$i$ 行目には、$c_i$ を取り除いた場合の合計スコアを出力してください。

入出力例

入力 1

5
LRLDD

出力 1

14
11
14
16
16