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

---

دوره ۱۰۲۸ ایا که به این حجم از فعالیت‌های شاز در دوره ۲۸ مشکوک شده بودند، دریافتند که دوره ۲۸ ایا کپی می‌کردند! با بررسی‌های فراوان معلوم شد که دوره ۲۸ ایا برای این کار ابتدا $n$ چیز روی صفحه می‌نوشتند و سپس در شب $i$ ام بازه $l_i$ تا $r_i$ را در بین چیز $k_i$ ام و $k_i+1$ ام کپی می‌کردند‌‌.

فرض کنید تعداد چیز ها قبل از انجام عملیات کپی در شب $i$ ام $N_i$ باشد. یعنی:

$$\ N_1=n \ , \ N_i+r_i-l_i+1=N_{i+1} \ $$

می دانیم اگر $k_i=0$ باشد در ابتدای چیز‌ها کپی می‌کردند و اگر $k_i=N_i$ در انتهای چیز‌ها کپی می‌کردند‌). دوره ۲۸ ایا بعد از هر کپی شبانه خود متن بدست آمده را به عنوان پست در بلاگ شاز متنشر می‌کردند! (دوره ۱۰۲۸ ایا از فعالیت‌های شاز مات و مبهوت مانده بودند، سعی داشتند با خذعبلات منتشر شده از ذهن کثیفشان! خود را توجیه کرده و کار‌های دوره ۲۸ ایا را بی‌ارزش سازند).

دوره ۱۰۲۸ ایا توانسته بودند (‌به خیال خام خود!) نحوه کپی کردن پست‌ها را بدست آورند. آنها ارزش مطالب دوره ۲۸ ایا را می‌دانستند. اما دیدند که فعالیت شاز آنقدر زیاد بوده که در سال ۲۳۹۷ نیز اگر تمام توان خود را جمع می‌کردند، نمی‌توانستند $10^{18}$ چیز تشکیل‌دهنده پست شاز را تفسیر کنند. (برای این که بفهمید $10^{18}$ چقدر بزرگ است، کافیست تعداد میکرو ثانیه‌های مانده تا سال ۲۳۹۷ را حساب کنید!) به همین خاطر تصمیم گرفتند به جمع چیز‌های تشکیل‌دهنده پست‌های شاز به پیمانه $10^9+7$ بسنده کنند.

ورودی

در سطر اول $n$ می‌آید و در سطر دوم یک آرایه $n$ تایی $a_i$ می‌آید که همان چیز‌های اولیه هستند.
در سطر سوم $q$ که تعداد پست‌های اولیه شاز است می‌آید و در $q$ سطر بعد در هر سطر $l_i$ و $r_i$ و $k_i$ می‌آیند.

$$ 0 \leq a_i \leq 10^9 $$ $$ 1 \leq n,q \leq 50\ 000$$ $$ 1 \leq l_i \leq r_i \leq N_i \leq 10^{18} $$$$ 0 \leq k_i \leq N_i $$

خروجی

در $q$ سطر در هر سطر جمع چیز‌های پست شاز در آن شب (بعد از هر کپی کردن) را خروجی دهید.

مثال

ورودی نمونه ۱

5
1 3 6 4 6 
5
2 4 1
2 8 2
9 13 13
1 13 12
8 25 3

خروجی نمونه ۱

33
65
90
145
223

ورودی نمونه ۲

5
523678577 195438412 597619564 103402540 338592606 
5
2 2 0
1 6 6
3 7 4
7 16 3
8 25 24

خروجی نمونه ۲

954170104
908340201
338831721
33837909
970289194