+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- > صورت این سوال نسبتا‌ً طولانی بود و نمی‌توانستیم شخصیت خاصی را داخلش جا بدهیم، اما نوبت *باب* است و اگر در سوال نباشد ناراحت می‌شود پس مجبور شدیم یک جایی در این سوال اسمش را بیاوریم. *قدرت* دنباله‌ی اعداد $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 ```