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

حاجی فیروز تصمیم گرفته برای کمک به نوروز در مزرعه سیری مشغول به کار شود. او شروع کرد به برداشت سیرها و هر مقدار سیری را که در ساعت $i$امش برداشت کرد در گونی‌ شماره $i$ قرار می‌دهد. بعد از اتمام برداشت سیرها متوجه می‌شود در ساعت $i$ام توانسته $a_i$ سیر برداشت کند.

سیر نماد قناعت، مناعت طبع است.

حاجی فیروز که همیشه دنبال پیشرفت است، مقدار پیشرفتش در برداشت سیر در ساعت $i$ام ($1 \lt i$) را برابر مقدار زیر قرار می‌دهد. $$max(0, a_i - max_{1 \le j \lt i} a_j)$$

که ناگهان $q$ سوال بسیار مهم به ذهن حاجی فیروز رسید. سوال‌های حاجی فیروز دو نوع بودند.

• نوع اول: «چی می‌شد اگر تو ساعت کاری $i$ عوض انقدری که سیر برداشت کردم $x$ سیر برداشت می‌کردم؟»
• نوع دوم: «الان مجموع پیشرفت من از ساعت $l$ تا ساعت $r$ چقدر است؟» (دقت کنید که پیشرفت در ساعت‌های $l$ام و $r$ام هم حساب هستند.)

حواستان باشد که وقتی حاجی فیروز سؤالی از نوع دوم از خودش می‌پرسد تمام تغییراتی که سوال‌های نوع اول که قبل از این سوال به ذهن او خطور کرده است در ذهن او اعمال شده‌اند.

به حاجی فیروز کمک کنید تا به پاسخ سؤال‌هایش برسد.

ورودی

در سطر اول دو عدد صحیح $n$ و $q$ به‌ترتیب می‌آیند.
در سطر دوم $n$ عدد صحیح $a_1, a_2, a_3, \cdots, a_n,,$ به‌ترتیب می‌آیند.
در هر یک از $q$ سطر بعدی سوال‌های حاجی فیروز می‌آیند که هر کدام به یکی از دو شکل زیر است:

• نوع اول: سه عدد $1$ و $i$ و $x$ به‌ترتیب می‌آیند.
• نوع دوم: سه عدد $2$ و $l$ و $r$ به‌ترتیب می‌آیند.

$$1 \le n, q \le 2 \times 10^5$$ $$0 \le a_i \le 10^9$$ $$1\le i \le n, \quad \quad 0\le x \le 10^9$$ $$2\le l \le r \le n$$

خروجی

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

مثال‌ها

ورودی نمونه ۱

5 5
1 5 2 3 5
2 2 5
1 2 2
2 2 5
1 1 2
2 2 5

خروجی نمونه ۱

4
4
3

در اولین سوال از سوال‌های نوع دوم میزان پیشرفت در ساعت دوم برابر ۴ است، میزان پیشرفت در ساعت سوم ۰ است، میزان پیشرفت در ساعت چهارم ۰ است و میزان پیشرفت در ساعت پنجم نیز ۰ است.

در دومین سوال از سوال‌های نوع دوم میزان پیشرفت در ساعت دوم برابر ۱ است، میزان پیشرفت در ساعت سوم ۰ است، میزان پیشرفت در ساعت چهارم ۱ است و میزان پیشرفت در ساعت پنجم نیز ۲ است.

در سومین سوال از سوال‌های نوع دوم میزان پیشرفت در ساعت دوم برابر ۰ است، میزان پیشرفت در ساعت سوم ۰ است، میزان پیشرفت در ساعت چهارم ۱ است و میزان پیشرفت در ساعت پنجم نیز ۲ است.

ورودی نمونه ۲

8 8
4 3 7 2 11 5 14 18
2 3 7
2 2 4
1 3 12
2 3 8
2 2 5
1 7 2
1 8 1
2 4 8

خروجی نمونه ۲

10
3
14
8
0