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

---

صورت این سوال نسبتا‌ً طولانی بود و نمی‌توانستیم شخصیت خاصی را داخلش جا بدهیم، اما نوبت باب است و اگر در سوال نباشد ناراحت می‌شود پس مجبور شدیم یک جایی در این سوال اسمش را بیاوریم.

قدرت دنباله‌ی اعداد $a_1,a_2,...,a_n$ برابر مجموع زیبایی تمام افراز های آن به تعدادی بخش (نه لزومن متوالی) است.

زیبایی افراز یک دنباله به تعدادی بخش برابر: $$\sum_{i=1}^k s_{i} \times p_{c_{i}}$$ است که در آن $s_i$ برابر مجموع اعداد بخش $i$-ام از افراز است و $c_i$ برابر تعداد اعضای بخش $i$-ام از افراز است و $k$ تعداد بخش‌های افراز است و $p_1,p_2,...,p_n$ دنباله دیگری است که به صورت جداگانه در ورودی داده می‌شود. دقت کنید که اعداد برچسب‌دار هستند، یعنی دو عدد برابر در دنباله متفاوت هستند. برای مثال در دنباله‌ی $[1,2,2]$ افراز $[[1,2],[2]]$ دو بار شمارده‌ می‌شود، یک بار برای اوّلین $2$ یک بار هم برای دوّمین $2$ شمارده‌ می‌شود.

در هر عملیات ما می‌توانیم دو عضو از آرایه را انتخاب کنیم و $m$ واحد (عددی صحیح دلخواه) به یکی از آن‌ها اضافه کنیم و $m$ واحد از دیگری کم کنیم (بعد از یک عملیات ممکن است عضوی از آرایه منفی شود).

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

باب به شما دنباله‌ی $a_1,a_2,...,a_n$ و دنباله‌ی $p_1,p_2,...,p_n$ را داده‌ است و سپس $q$ درخواست به شما می‌دهد، که هر درخواست به یکی از اشکال زیر است :

1. به شما سه عدد $l \ r \ x$ داده‌ می‌شود و از شما می‌خواهد که تمام اعداد $a_{l},...,a_r$ را $x$ واحد افزایش دهید.
2. به شما دو عدد $l \ r$ داده ‌می‌شود و از شما می‌خواهد که قدرت‌محض دنباله‌ی $a_{l},...,a_r$ را خروجی‌دهید.

به دلیل این که قدرت‌محض دنباله می‌تواند بزرگ باشد، باقی‌مانده‌اش را در تقسیم آن بر $10^9+7$ را خروجی دهید. دقت کنید که فقط در انتها با‌قی‌مانده گرفته می‌شود و در تمام مراحل بدست آوردن قدرت‌محض، خود اعداد در نظر گرفته‌ می‌شوند و بزرگی باقی‌مانده آن‌ها در تقسیم بر $10^9+7$ مد نظر نیست.

ورودی

در خط اول ابتدا $n$ که تعداد اعضای دنباله‌ی $a$ و $p$ است و سپس $q$ که تعداد در‌خواست‌ها است داده‌ ‌می‌شود. سپس در خط بعدی $n$ عدد به‌ شما داده می‌شود که عدد $i$-ام همان $a_i$ است. سپس در خط بعدی $n$ عدد به‌ شما داده می‌شود که عدد $i$-ام همان $p_i$ است. سپس در $q$ خط بعدی به شما در‌خواست‌ها داده‌ می‌شود که به‌ صورت زیر داده‌ می‌شود:

1. به صورت $1 \ l \ r \ x$ داده‌ ‌می‌شود که همان درخواست نوع اول است.
2. به صورت $2 \ l \ r$ داده ‌می‌شود که همان در‌خواست نوع دوم است.

$$1 \le n \le 5 \ 000$$ $$1 \le q \le 500 \ 000$$ $$0 \le a_i,p_i,x \le 10^9$$ $$1\le l \le r \le n$$

خروجی

در خروجی به ازای هر درخواست نوع دوم باقی‌مانده قدرت‌محض آن بخش خواسته‌شده بر $10^9+7$ را چاپ کنید.

مثال

ورودی نمونه ۱

3 3
1 2 3
6 3 2
2 1 3
1 1 3 1
2 1 3

خروجی نمونه ۱

120
180

توضیح برای درخواست اوّل: اگر دنباله را به $[3,0,3]$ تبدیل کنیم، قدرت آن ماکسیمم می‌شود:

• قدرت $[[3,0,3]]$ برابر $12$ است.
• قدرت $[[3,0],[3]]$ برابر $27$ است.
• قدرت $[[0,3],[3]]$ برابر $27$ است.
• قدرت $[[3,3],[0]]$ برابر $18$ است.
• قدرت $[[3],[0],[3]]$ برابر $36$ است.

که قدرت‌محض آن می‌شود : $12+27+27+18+36=120$

توضیح برای درخواست دوّم: اعضای اوّل تا سوّم دنباله یک واحد افزایش پیدا میکنند و دنباله‌ی $[1, 2, 3]$ به دنباله‌ی $[2, 3, 4]$ تغییر پیدا می‌کند.

توضیح برای درخواست سوّم: اگر دنباله را به $[4,0,5]$ تبدیل کنیم، قدرت آن ماکسیمم می‌شود:

• قدرت $[[4,0,5]]$ برابر $18$ است.
• قدرت $[[5,0],[4]]$ برابر $39$ است.
• قدرت $[[4,0],[5]]$ برابر $42$ است.
• قدرت $[[4,5],[0]]$ برابر $27$ است.
• قدرت $[[5],[0],[4]]$ برابر $54$ است.

که قدرت‌محض آن می‌شود : $18+39+42+27+54=180$

ورودی نمونه ۲

3 3
1 2 3
6 3 3
1 1 2 2
1 1 3 3
2 1 3

خروجی نمونه ۲

399