Динамічна подільність

Limits: 4 sec., 512 MiB

Зеник записав на шматку паперу ціле число із $n$ цифр, $i$-та з яких початково рівна $d_i$ ($1 \le i \le n$, нумерація зліва направо). Марічка ж загадала одне ціле число $k$.

Тепер вони хочуть опрацювати $q$ операцій, кожна з яких описана трьома числами $l_i$, $r_i$ та $c_i$. Для кожної операції вони виконують наступні дії:

1. Зеник вирізає послідовність цифр від $l_i$-ї до $r_i$-ї включно.

2. Далі, він склеює усі інші цифри разом, зберігаючи їх відносний порядок.

3. Після цього, він вставляє вирізаний проміжок цифр одразу після перших $c_i$ цифр, посунувши усі наступні цифри. Таким чином, він утворює нове число із рівно $n$ цифр.

4. Після цього, Марічка знаходить одне ціле число — остачу від ділення записаного зараз на папері числа на $k$.

Допоможіть їм знайти відповіді після виконання усіх операцій в заданому порядку.

Зауважте, що число, яке записне на папері, може містити ведучі нулі.

Input

У першому рядку задано три цілих числа $n$, $k$ та $q$ — кількість цифр, число, остачу від ділення на яке знаходить Марічка та кількість операцій відповідно.

У другому рядку задано послідовність із $n$ цифр $d_i$ (без пробілів) — початкове число.

У наступних $q$ рядках описано операції в порядку їх виконання. Опис кожної операції складається із трьох чисел, розділених пробілами — $l_i$, $r_i$ та $c_i$.

Output

Для кожної операції виведіть одне ціле число в окремому рядку — остачу від ділення поточного числа на $k$.

Constraints

$1 \le n, q \le 2 \cdot 10^5$,

$1 \le k \le 10^9$,

$0 \le d_i \le 9$,

$1 \le l_i \le r_i \le n$,

$0 \le c_i \le n-(r_i-l_i+1)$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1000000000 4 12345 2 4 2 1 2 1 3 5 0 2 2 2	15234 21534 53421 54321

Input (stdin) сopy	Output (stdout) сopy
14 83 7 33758621355151 6 8 1 2 10 3 11 14 6 3 8 8 2 11 4 7 12 6 2 13 0	27 1 62 6 60 60 6