• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

---

شیرین عسل به کل دست از سر یار برداشته و قصد پرداختن به کار علمی دارد.

او در آزمایشگاه خود $n$ موش آزمایشگاهی دارد که هر کدام مقداری سلامتی دارند و با شماره‌های $1$ تا $n$ شماره گذاری شده اند. در ابتدا، در پایان هر روز که ‌می‌گذرد $1$ واحد از سلامتی هر موش کم می‌شود.

شیرین عسل در ابتدایِ هر روز یکی از کارهای زیر را انجام می‌دهد:

1. تعداد موش‌های زنده از موشِ $l$ام تا $r$ام را می‌پرسد.
2. به موش $i$ام یک ویروس با قدرت $val$ می‌دهد که باعث می‌شود از آن روز به بعد در پایان هر روز $val$ واحد بیشتر از قبل از سلامتی موش کم شود (یعنی اگر تا قبل از ویروس دادن هر روز $x$ واحد از سلامتی‌اش کم می‌شد از این به بعد هر روز $x + val$ واحد کم می‌شود).

منطقن هر موشی که سلامتی‌اش به صفر برسد یا منفی شود دیگر زنده نیست.

شما باید جواب سوال‌های شیرین عسل را بدهید.

ورودی

در سطر اول ورودی دو عدد طبیعی $n$ و $q$ با فاصله آمده‌اند که به ترتیب نمایانگر تعداد موش‌ها و تعداد روز‌هایی که شیرین عسل در آزمایشگاه مشغول است هستند. در سطر دوم $n$ عدد ($a_1...a_n$) با فاصله آمده‌اند که $a_i$ سلامتی موش $i$ام است. در $q$ سطر بعدی فعالیت‌های شیرین عسل در هر روز به ترتیب و به صورت ? l r یا + i val آمده است (هر روز در یک سطر).

$$ 1 \le n, q \le 400\ 000 $$ $$ 1 \le a_i \le 1\ 000\ 000\ 000 $$ $$ 1 \le l \le r \le n $$ $$ 1 \le i \le n $$ $$ 1 \le val \le 100\ 000 $$

خروجی

به ترتیب به ازای هر پرسش جواب را در یک خط چاپ کنید.

مثال

ورودی نمونه ۱

5 7
3 1 8 4 2
? 1 5
? 1 5
+ 4 1
? 2 5
+ 3 2
? 2 5
? 2 5

خروجی نمونه ۱

5
4
1
1
0