Табун лошадей
Мансур любит разводить лошадей, как и его предки. Сейчас у него самый большой табун в Казахстане, но так было далеко не всегда. 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), которое Мансур смог бы заработать с учетом этого уточнения.