Динамічна подільність
Limits: 4 sec., 512 MiB
Зеник записав на шматку паперу ціле число із \(n\) цифр, \(i\)-та з яких початково рівна \(d_i\) (\(1 \le i \le n\), нумерація зліва направо). Марічка ж загадала одне ціле число \(k\).
Тепер вони хочуть опрацювати \(q\) операцій, кожна з яких описана трьома числами \(l_i\), \(r_i\) та \(c_i\). Для кожної операції вони виконують наступні дії:
Зеник вирізає послідовність цифр від \(l_i\)-ї до \(r_i\)-ї включно.
Далі, він склеює усі інші цифри разом, зберігаючи їх відносний порядок.
Після цього, він вставляє вирізаний проміжок цифр одразу після перших \(c_i\) цифр, посунувши усі наступні цифри. Таким чином, він утворює нове число із рівно \(n\) цифр.
Після цього, Марічка знаходить одне ціле число — остачу від ділення записаного зараз на папері числа на \(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) | Output (stdout) |
|---|---|
| 5 1000000000 4 12345 2 4 2 1 2 1 3 5 0 2 2 2 | 15234 21534 53421 54321 |
| Input (stdin) | Output (stdout) |
|---|---|
| 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 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|