有一个无限大的二维棋盘，其中每个格子都有唯一的整数坐标 $(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