Позсовуйте

Обмеження: 2 сек., 512 МіБ

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Обмеження

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

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

Приклади