• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

---

مادربزرگ می خواهد به مناسبت کسب مدال طلای جهانی(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

(آزمون آزمایشی ۲۴ مین دوره المپیاد کامپیوتر-دوره تابستان المپیاد کامپیوتر ۱۳۹۳)