Табун коней
Мансур захоплюється розведенням коней, як і його предки. Зараз у нього найбільший табун у Казахстані, але так було не завжди. n років тому Мансур був простим джигітом (молодий чоловік по-казахськи) і мав лише одну коняку. Він мріяв заробити багато грошей і стати баєм (дуже багатий чоловік по-казахськи).
Пронумеруємо роки від 0 до n - 1 в хронологічному порядку (тобто так, що номер минулого року n - 1). Кожного року погода впливала на приріст табуна. Для кожного i-го року Мансур пам'ятає ціле додатне число x[i] - коефіцієнт приросту. Якщо на початку i-го року було h коней, то в кінці цього ж року в табуні ставало h * x[i] коней.
Коней можна було продавати лише в кінці року. Для кожного i-го року Мансур пам'ятає ціле додатне число y[i] - ціну однієї коня в кінці цього року. В кінці кожного i-го року можна було продати будь-яку кількість коней, кожну за ціною y[i].
Мансур хоче дізнатися максимальну кількість грошей, яку він зміг би заробити, продаючи своїх коней у найвідповідніші моменти протягом n років. Ви удостоєні честі бути гостем на "той" Мансура (свято по-казахськи), і він просить відповісти на це питання.
Іноді Мансур згадує деталі, з яких формується послідовність з m уточнень. Кожне уточнення стосується одного з значень x[i] або y[i]. Після кожного уточнення він знову просить порахувати максимальну кількість грошей, яку він міг би заробити, продаючи коней. Уточнення застосовуються послідовно, тому кожна відповідь на прохання повинна враховувати всі попередні уточнення. Зазначимо, що кожне з значень x[i] або y[i] можуть бути уточнені кілька разів.
Відповіді на питання Мансура можуть бути дуже великими числами. Щоб уникнути дій з величезними числами, необхідно дати відповідь по модулю 10^9 + 7.
Приклад
Припустимо, що пройшло три роки (n = 3) і мається наступна інформація:
При таких початкових значеннях Мансур заробить максимальну кількість грошей, продавши обидві коні в кінці року з номером 1. Послідовність його дій така:
Спочатку у Мансура одна кінь.
В кінці року з номером 0 у нього буде дві коні (1 *
X[0]= 2).В кінці року з номером 1 у нього все ще буде дві коні (2 *
X[1]= 2), зараз він може їх продати, його вигода складе 8 (2 *Y[1]= 8).
Після цього відбулося одне уточнення (m = 1), і значення y[1] стало рівним 2. Після уточнення маємо наступну інформацію:
У такому випадку, одне з оптимальних рішень - продати одну коня в кінці року з номером 0 і три коні в кінці року з номером 2. Послідовність дій така:
Спочатку у Мансура одна кінь.
В кінці року з номером 0 у нього буде дві коні (1 *
X[0]= 2), зараз він може продати одну коня, його вигода складе 3 (1 *Y[0]= 3). У нього залишиться одна кінь.В кінці року з номером 1 у нього буде одна кінь (1 *
X[1]= 1).В кінці року з номером 2 у нього буде три коні (1 *
X[2]= 3), зараз він може продати три коні, його вигода складе 3 (3 *Y[2]= 3). Таким чином, максимальна сумарна кількість грошей дорівнює 6 (3 + 3 = 6).
Вхідні дані
Перша рядок містить кількість минулих років n (1 ≤ n ≤ 500000). Друга рядок задає коефіцієнти приросту x[0], x[1], ... x[n-1] в кінці i-го року (0 ≤ i ≤ n - 1), а третя задає ціни y[0], y[1], ... y[n-1] однієї коня в кінці i-го року (0 ≤ i ≤ n - 1). Наступна рядок містить кількість уточнень m (1 ≤ m ≤ 10^5). Кожна з наступних m рядків містить три числа type pos val (type = 1 для UpdateX, type = 2 для UpdateY, 0 ≤ pos ≤ n - 1). Як початкові, так і уточнені значення масивів X і Y знаходяться в діапазоні від 1 до 10^9 включно.
Вихідні дані
У першому рядку вивести максимальну кількість грошей (по модулю 10^9 + 7), яку Мансур зміг би заробити при початкових значеннях X і Y. Далі для кожного уточнення вивести максимальну кількість грошей (по модулю 10^9 + 7), яку Мансур зміг би заробити з урахуванням цього уточнення.