Atlar sürüsü#7769
Mənsur at yetişdirməyi, eləcə də onun əcdadları kimi sevir. Hazırda onun Qazaxıstanda ən böyük at sürüsü var, amma bu həmişə belə olmayıb. n il əvvəl Mənsur sadə bir cigit idi (qazax dilində gənc oğlan) və onun cəmi bir atı var idi. O, çox pul qazanmağı və bay (qazax dilində çox varlı adam) olmağı arzulayırdı.
İlləri 0-dan n - 1-ə qədər xronoloji ardıcıllıqla nömrələyək (yəni keçən ilin nömrəsi n - 1). Hər il hava şəraiti sürünün artımına təsir edirdi. Hər bir i-ci il üçün Mənsur artım əmsalı olan müsbət tam ədəd x[i]-ni xatırlayır. Əgər ilin əvvəlində h at var idisə, ilin sonunda sürüdə h * x[i] at olurdu.
Atları yalnız ilin sonunda satmaq mümkün idi. Hər bir i-ci il üçün Mənsur ilin sonunda bir atın qiyməti olan müsbət tam ədəd y[i]-ni xatırlayır. Hər bir i-ci ilin sonunda istənilən sayda atı satmaq mümkün idi, hər biri y[i] qiymətinə.
Mənsur n il ərzində atlarını ən uyğun vaxtlarda sataraq qazana biləcəyi maksimum pul miqdarını bilmək istəyir. Siz Mənsurun toyunda (qazax dilində bayram) qonaq olmaq şərəfinə layiq görülmüsünüz və o, sizdən bu suala cavab verməyinizi xahiş edir.
Bəzən Mənsur xatırlayır ki, müəyyən detallardan ibarət olan m dəqiqləşdirmə ardıcıllığı var. Hər bir dəqiqləşdirmə x[i] və ya y[i] dəyərlərindən birinə aiddir. Hər bir dəqiqləşdirmədən sonra o, yenidən atlarını sataraq qazana biləcəyi maksimum pul miqdarını hesablamağı xahiş edir. Dəqiqləşdirmələr ardıcıl tətbiq olunur, buna görə də hər bir xahişə cavab əvvəlki dəqiqləşdirmələri nəzərə almalıdır. Qeyd edək ki, x[i] və ya y[i] dəyərləri bir neçə dəfə dəqiqləşdirilə bilər.
Mənsurun suallarına cavablar çox böyük ədədlər ola bilər. Böyük ədədlərlə əməliyyatlardan qaçmaq üçün 10^9 + 7 moduluna görə cavab vermək lazımdır.
Tutaq ki, üç il keçib (n = 3) və aşağıdakı məlumatlar var:
Bu ilkin dəyərlərlə Mənsur maksimum pul miqdarını, hər iki atı ilin 1 nömrəli sonunda sataraq qazanacaq. Onun hərəkət ardıcıllığı belədir:
Əvvəlcə Mənsurun bir atı var.
0 nömrəli ilin sonunda onun iki atı olacaq (1 * X[0] = 2).
1 nömrəli ilin sonunda onun hələ də iki atı olacaq (2 * X[1] = 2), indi onları sata bilər, onun qazancı 8 olacaq (2 * Y[1] = 8).
Bundan sonra bir dəqiqləşdirmə oldu (m = 1), və y[1] dəyəri 2 oldu. Dəqiqləşmədən sonra aşağıdakı məlumatlar var:
Bu halda, optimal həllərdən biri 0 nömrəli ilin sonunda bir at satmaq və 2 nömrəli ilin sonunda üç at satmaqdır. Hərəkət ardıcıllığı belədir:
Əvvəlcə Mənsurun bir atı var.
0 nömrəli ilin sonunda onun iki atı olacaq (1 * X[0] = 2), indi bir at sata bilər, onun qazancı 3 olacaq (1 * Y[0] = 3). Onun bir atı qalacaq.
1 nömrəli ilin sonunda onun bir atı olacaq (1 * X[1] = 1).
2 nömrəli ilin sonunda onun üç atı olacaq (1 * X[2] = 3), indi üç at sata bilər, onun qazancı 3 olacaq (3 * Y[2] = 3). Beləliklə, maksimum ümumi pul miqdarı 6 olacaq (3 + 3 = 6).
Birinci sətir keçən illərin sayını n (1 ≤ n ≤ 500000) ehtiva edir. İkinci sətir hər bir ilin sonunda artım əmsalları x[0], x[1], ... x[n-1]-i (0 ≤ i ≤ n - 1) təyin edir, üçüncü sətir isə hər bir ilin sonunda bir atın qiymətləri y[0], y[1], ... y[n-1]-i (0 ≤ i ≤ n - 1) təyin edir. Növbəti sətir dəqiqləşdirmələrin sayını m (1 ≤ m ≤ 10^5) ehtiva edir. Növbəti m sətirin hər biri üç ədəd type pos val (type = 1 üçün UpdateX, type = 2 üçün UpdateY, 0 ≤ pos ≤ n - 1) ehtiva edir. Həm ilkin, həm də dəqiqləşdirilmiş X və Y massivlərinin dəyərləri 1-dən 10^9-a qədər daxilindədir.
Birinci sətirdə Mənsurun X və Y-nin ilkin dəyərləri ilə qazana biləcəyi maksimum pul miqdarını (10^9 + 7 moduluna görə) çıxarın. Sonra hər bir dəqiqləşdirmə üçün Mənsurun bu dəqiqləşməni nəzərə alaraq qazana biləcəyi maksimum pul miqdarını (10^9 + 7 moduluna görə) çıxarın.
Nümunə 1