+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر ---------- مادربزرگ می خواهد به مناسبت کسب مدال طلای جهانی(*fullmark*) توسط تمامی $n$ نوه اش به آنها جایزه بدهد. او آنها را پشت سر هم در یک ردیف و از چپ به راست نشانده است. مادربزرگ کمی حواس پرت هست و به طور ناگهانی یادش می آید که باید به بازه $l$ تا $r$ از نوه هایش جایزه بدهد و برای این کار به نفر اول(نفر $l$ ام) یک سکه به نفر بعد ۲ سکه و به نفر آخر(نفر $r$ ام) $r - l + 1$ سکه می دهد. هر از گاهی هم مادربزرگ کنجکاو است که بداند مجموع تعداد سکه های بازه $l$ تا $r$ از نوه هایش چقدر می باشد.به مادربزرگ کمک کنید! # ورودی در خط اول ورودی دو عدد $n$ و $q$ آمده است که تعداد نوه های مادربزرگ و تعداد عملیات های مادربزرگ می باشد! در خط بعدی $n$ عدد آمده است که تعداد سکه های اولیه نوه های مادربزرگ به ترتیب از چپ به راست می باشد.این اعداد بین $0$ تا $10^9$ می باشند. در $q$ خط بعدی در هر خط ابتدا رشته $t$ و سپس $l$ و $r$ آمده است. اگر $t=ask$ باقیمانده مجموع تعداد سکه های نوه های بین بازه $l$ تا $r$ بر $10^9+7$ را چاپ کنید. اگر $t=add$ مادربزرگ به بازه ی $l$ تا $r$ از نوه هایش به شکل گفته شده سکه می دهد. $$1 \le l \le r \le n \le 200\ 000$$ # خروجی به ازای هر یک از عملیات های $ask$ جواب را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $1\le n,q \le 2\ 000$ | | ۲ | ۲۰ | $,1\le n \le 2\ 000$ $1 \le q \le 200\ 000$ | | ۳ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 10 4 7 4 7 4 ask 1 5 add 1 2 ask 2 4 add 3 5 ask 4 5 add 2 5 add 3 3 ask 3 3 ask 2 5 ask 1 5 ``` ## خروجی نمونه ۱ ``` 26 20 16 8 41 46 ``` (آزمون آزمایشی ۲۴ مین دوره المپیاد کامپیوتر-دوره تابستان المپیاد کامپیوتر ۱۳۹۳)