Відра

Limits: 4 sec., 256 MiB

У Зеника є \(n\) склянок з водою, пронумерованих від 1 до \(n\). В \(i\)-ій склянці є \(a_i\) мілілітрів води. Також він має нескінченну кількість відер місткістю \(m\) мілілітрів.

Розглянемо послідовність склянок \([b_1, b_2, \dots, b_k]\) (\(b_j\) позначає об’єм води в мілілітрах в \(j\)-ій склянці), у якої для всіх \(j\) виконується \(1 \le b_j \le m\). Визначимо відерність цієї послідовності, як кількість відер, які використає Зеник при такому процесі.

1. Зеник бере нове порожнє відро.

2. Якщо всі склянки порожні, Зеник переходить до пункту 6.

3. Зеник бере непорожню склянку з найменшим номером \(j\) (\(1 \le j \le k\)).

4. Якщо у відро, яке Зеник тримає в руках, поміститься ще \(b_j\) мілілітрів води, він виливає всю воду з \(j\)-ої склянки в це відро та переходить до пункту 2.

5. Зеник відкладає набік відро, яке тримає в руках, бере нове порожнє відро та переходить до пункту 2.

6. Кінець.

Марічка поставила Зенику \(q\) завдань двох типів.

• 1 \(l\) \(r\) — порахувати відерність послідовності \([a_l, a_{l+1}, \dots, a_r]\).

• 2 \(p\) \(x\) — змінити значення \(a_p\) на \(x\).

У завданні першого типу Зеник насправді не спорожнює склянки, а тільки рахує відерність.

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

Input

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

Другий рядок містить \(n\) цілих чисел \(a_i\) — об’єми води в мілілітрах у склянках.

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

У наступних \(q\) рядках описано завдання у вищенаведеному форматі.

Output

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

Constraints

\(1 \le n \le 10^5\),

\(1 \le m \le 10^9\),

\(1 \le a_i \le m\),

\(1 \le q \le 10^5\),

\(1 \le l \le r \le n\),

\(1 \le p \le n\),

\(1 \le x \le m\).

Оцінювання задачі складається з наступних блоків:

5 балів — \(1 \le n, q \le 2 \cdot 10^3\),

10 балів — є тільки завдання першого типу,

10 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 47 4 10 40 4 4 7 36 7 1 1 7 1 4 7 2 3 28 1 1 5 1 3 3 2 4 44 1 4 7	3 2 2 1 2

Notes

Порахуємо відерність послідовності \([4, 10, 40, 4, 4, 7, 36]\) при \(m=47\).

• Зеник бере перше порожнє відро.

• Виливає воду з першої склянки у відро. Тепер у відрі 4 мл води.

• Виливає воду з другої склянки у відро. У відрі 14 мл води.

• Вода з третьої склянки не поміщається у відро. Зеник бере друге нове відро та виливає туди воду з третьої склянки. У відрі тепер 40 мл води.

• Зеник виливає воду із четвертої склянки у відро, тепер там 44 мл.

• Вода з п’ятої склянки не поміщається у відро. Зеник бере третє нове відро та виливає туди воду з п’ятої склянки. У відрі тепер 4 мл води.

• Зеник виливає воду із шостої склянки у відро, тепер там 11 мл.

• Зеник виливає воду із сьомої склянки у відро, тепер у відрі 47 мл.

Зеник використав три відра, отже відерність дорівнює 3.