Shift

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

In a row, there are \(n\) objects in \(n\) cells, numbered from \(1\) to \(n\). Initially, each object is in its own cell. To the left and right of them, there are two walls.

You are given a string of operations \(s\) consisting only of the characters L and R. If \(s_i = \verb|L|\), all objects shift one cell to the left, and if \(s_i = \verb|R|\) — to the right. If an object hits a wall, its position does not change. After these operations, multiple objects may end up in the same cell.

For a given string \(s\), find the answer to \(q\) queries.

What is the sum of the final positions of the elements if we simulate the process with \(n_i\) objects?

Input

The first line gives the string \(s\) consisting of characters L and R.

The second line gives a single integer \(q\) — the number of queries.

The next \(q\) lines each contain a single integer \(n_i\) — the query parameters.

Output

In \(q\) lines, print one integer for each query — the sum of the positions of the objects after all operations.

Constraints

\(1 \le |s|, n_i \le 10^6\),

\(1 \le q \le 2 \cdot 10^5\).

Samples