Позсовуйте

Limits: 2 sec., 512 MiB

У ряду стоять \(n\) об’єктів у \(n\) клітинках, пронумерованих від \(1\) до \(n\). Спочатку кожен об’єкт є у своїй клітинці. Зліва і справа від них є дві стіни.

Дано рядок операцій \(s\), що складається лише з символів L та R. Якщо \(s_i = \verb|L|\), то всі об’єкти зсунуться на одну клітинку ліворуч, якщо ж \(s_i = \verb|R|\) — праворуч. Якщо об’єкт впирається в стіну, то його позиція не змінюється. Після таких операцій декілька об’єктів можуть опинитися в одній клітинці.

За заданим рядком \(s\) знайдіть відповідь на \(q\) запитів.

Чому рівна сума фінальних позицій елементів, якщо просимулювати процес з \(n_i\) об’єктами.

Input

У першому рядку задано рядок \(s\) із символів L і R.

У другому рядку дано одне ціле число \(q\) — кількість запитів.

У наступних \(q\) рядках задано по одному цілому числу \(n_i\) — параметри запитів.

Output

У \(q\) рядках виведіть по одному цілому числу на кожен запит — суму позицій об’єктів після всіх операцій.

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
RLLRLRRRL 3 1 3 5	1 6 18