Có một bàn cờ 2 chiều vô hạn, trong đó mỗi ô có một tọa độ nguyên duy nhất $(x, y)$. Ô bắt đầu có tọa độ $(0, 0)$. Nếu chúng ta bắt đầu từ ô này, đi $x$ bước sang phải, và sau đó đi $y$ bước lên trên, chúng ta sẽ đến ô $(x, y)$. Lưu ý rằng $x$ và $y$ có thể âm, nghĩa là đi theo hướng ngược lại.

Có một robot bắt đầu từ ô $(0, 0)$ và thực hiện một chuỗi lệnh $c_1 c_2 \dots c_n$, trong đó mỗi $c_i \in \{\text{L, R, D, U}\}$, tương ứng với việc đi một bước theo hướng Trái, Phải, Xuống, Lên. Ví dụ, nếu chuỗi lệnh là LRLD, thì các ô đã đi qua là $(0, 0) \to (-1, 0) \to (0, 0) \to (-1, 0) \to (-1, -1)$. Chúng ta gọi chuỗi này là lịch sử di chuyển của robot (trong ví dụ này, lịch sử chứa năm phần tử).

Với mỗi ô $(x, y)$ trong lịch sử di chuyển, nếu đây là lần thứ $i$ robot ghé thăm ô này, robot sẽ nhận được số điểm là: $$f(x, y, i) = i \cdot ((|x| + 1) \oplus (|y| + 1)) + i$$

Tổng điểm là tổng số điểm của mọi ô trong lịch sử di chuyển. Trong ví dụ này, tổng điểm là $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$.

Với mỗi $i$ từ 1 đến $n$, hãy trả lời: nếu chúng ta loại bỏ $c_i$ khỏi chuỗi lệnh, tổng điểm mà robot nhận được sau khi thực hiện chuỗi lệnh còn lại $c_1 c_2 \dots c_{i-1} c_{i+1} \dots c_n$ là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 3 \cdot 10^5$). Dòng thứ hai chứa một chuỗi $c_1 c_2 \dots c_n$ có độ dài $n$, biểu thị chuỗi lệnh.

Dữ liệu ra

In ra $n$ dòng. Dòng thứ $i$ phải chứa tổng điểm nếu chúng ta loại bỏ lệnh $c_i$.

Ví dụ

Dữ liệu vào 1

5
LRLDD

Dữ liệu ra 1

14
11
14
16
16