+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- **دوره ۱۰۲۸ ایا** که به این حجم از فعالیت‌های شاز در دوره ۲۸ مشکوک شده بودند، دریافتند که **دوره ۲۸ ایا** کپی می‌کردند! با بررسی‌های فراوان معلوم شد که **دوره ۲۸ ایا** برای این کار ابتدا $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 ```