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

محمد توانسته داده‌های $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)$ نیز در ادامه خط آمده است که نشان دهنده عددی است که باید بازه را با آن جمع کرد. دقت کنید که اندیس عضو اول آرایه یک است.

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

• زیرمسئله اول (۸ نمره): $n,q \leq 5000$
• زیرمسئله دوم (۴۲ نمره):

به ازای تمام خط‌هایی که $t_i = ?$ داریم: $l_i=1$ و $r_i=n$

• زیرمسئله سوم (۳۵ نمره):$n,q \leq 10^5$
• زیرمسئله چهارم (۱۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n \le 10^5$
• \item $1 \leq n \leq 3 \times 10^5$
• \item $1 \leq q \leq 3 \times 10^5$
• \item $-10^9 \leq a_i \leq 10^9$
• \item $-10^9 \leq x_i \leq 10^9$
• \item $1 \leq l_i \leq r_i \leq n$

• سوال قبل