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

---

محمد بعد از تلاش‌های فراوان بالاخره موفق شد از بهترین دانشگاه دنیا پذیرش بگیرد. ولی از آن‌جایی که شانس با او یار نبود، همه‌گیری ویروس کرونا آغاز شد و مرزها و سفارت‌ها بسته شدند. حال بعد از گذشت ماه‌ها، دوباره بعضی از سفارت‌ها شروع به کار کرده‌اند و محمد امیدش به زندگی برگشته است اما سفارت‌ها به صورت بی‌برنامه کار خود را آغاز کرده‌اند.

محمد توانسته داده‌های $n$ روز اخیر سفارت را به دست آورد. در این داده‌ها، به ترتیب برای روز $i$ام، تعداد وقت‌های ملاقات که باز شده‌اند، آمده است. توجه کنید که این اعداد می‌توانند منفی باشند که به این معنا است که سفارت در آن روز تعدادی وقت ملاقات را کنسل کرده است. حال محمد متوجه شده است که بی‌برنامگی یک سفارت رابطه مستقیم با تعداد زیررشته‌های زیگزاگی از وقت‌های باز شده توسط سفارت دارد.

محمد متوجه شد که داده‌های سفارت از ابتدا درست نیستند و تغییراتی در آن‌ها به وجود می‌آید. همچنین برای او نیز در هنگام اعمال تغییرات سوال‌هایی در رابطه با تحلیل بی‌نظمی سفارت ایجاد می‌شود. در مجموع $q$ تغییر و پرسش برای داده‌های او رخ می‌دهد که یکی از سه حالت زیر هستند:

• عدد $x$ به اعداد روزهای $l$ تا $r$ اضافه شود.
• عدد $-1$ در اعداد روزهای $l$ تا $r$ ضرب شود.
• تعداد زیررشته‌های زیگزاگی روز‌های $l$ تا $r$ چندتا است.

دقت کنید که تمام تغییرات و سوالات شامل دو سر بازه خود می‌شوند، درواقع خود $l$ و $r$ نیز داخل بازه هستند. حال به محمد کمک کنید که پاسخ سوال‌هایش را پیدا کند تا زودتر بتواند مهاجرت کند و به آرزوهایش برسد و شما برای همیشه از سوال‌های او راحت شوید.

یک دنباله مثل $b_1, b_2, b_3, \cdots, b_k$ زیررشته‌ای از آرایه وقت‌های باز شده سفارت است اگر و فقط اگر، بتوان با حذف تعدادی دلخواه از روزها از انتها و ابتدای آرایه، این زیر رشته به دست آید.

یک دنباله مثل $b_1, b_2, b_3, \cdots, b_k$ زیگزاگی است اگر و تنها اگر یکی از دو شرط زیر را داشته باشد:

• $b_1 < b_2 > b_3 < b_4 > \cdots$
• $b_1 > b_2 < b_3 > b_4 < \cdots$

ورودی

در خط اول ورودی $n$ و $q$، تعداد روزهایی که محمد برای آن‌ها اطلاعات به دست آورده و مجموع تغییرات و سوالات می‌آید.

در خط دوم ورودی $a_1, a_2, \cdots, a_n$، که برابر با تعداد وقت‌های ملاقات باز شده توسط سفارت در هر روز است.

در خط $i$ام از هر یک از $q$ خط بعدی، ابتدا $ t_i \in {+, , ?}$ آمده است که $+$ به معنای عملیات نوع اول بر روی داده‌ها است، $$ نشان دهنده عملیات نوع دوم و $?$ نشان دهنده سوالی است که برای محمد پیش می‌آید. سپس دو عدد $l_i$ و $r_i$ ($ 1 \leq l_i \leq r_i \leq n$) آمده است که نشان‌ دهنده بازه‌ی مورد نظر است. اگر عملیات از نوع اول باشد، یک عدد $(-10^9 \leq x_i \leq 10^9)$ نیز در ادامه خط آمده است که نشان دهنده عددی است که باید بازه را با آن جمع کرد. دقت کنید که اندیس عضو اول آرایه یک است.

$$1 \leq n \leq 3 \times 10^5$$ $$1 \leq q \leq 3 \times 10^5$$ $$-10^9 \leq a_i \leq 10^9$$ $$-10^9 \leq x_i \leq 10^9$$ $$1 \leq l_i \leq r_i \leq n$$

خروجی

به ازای هر سوال محمد، تعداد زیررشته‌های زیگزاگی آن بازه را چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۸	$n,q \leq 5000$
۲	۴۲	به ازای تمام خط‌هایی که $t_i = ?$ داریم: $l_i=1$ و $r_i=n$
۳	۳۵	$n,q \leq 10^5$
۴	۱۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
2 3 -1 -1
? 1 4
+ 3 3 4
\* 1 3
? 2 4

خروجی نمونه ۱

7
4

ورودی نمونه ۲

6 8
-2 7 3 4 1 6
? 1 6
+ 3 5 4
\* 1 6
+ 5 6 -3
? 2 5
\* 3 5
+ 4 4 -2
? 3 6

خروجی نمونه ۲

21
5
10