Табун коней#7769

Табун коней

1 секунда

128 мегабайтів

Дуже легка

Мансур захоплюється розведенням коней, як і його предки. Зараз у нього найбільше стадо у Казахстані, але так було не завжди. $n$ років тому Мансур був простим джигітом і мав лише одного коня. Він мріяв заробити багато грошей і стати баєм.

Пронумеруємо роки від $0$ до $n - 1$ n - 1 у хронологічному порядку (тобто найсвіжіший рік має номер $n - 1$ n - 1). Щороку погода впливала на темпи приросту стада. Для кожного $i$ -го року Мансур пам'ятає додатне ціле число $x_{i}$ x_i — коефіцієнт приросту. Якщо на початку року $i$ у нього було $h$ коней, то наприкінці цього року стадо збільшувалось до $h \cdot x_{i}$ h \cdot x_i коней.

Коней можна було продавати лише наприкінці року. Для кожного $i$ -го року Мансур пам'ятає додатне ціле число $y_{i}$ y_i — ціну одного коня наприкінці цього року. Наприкінці кожного $i$ -го року можна було продати будь-яку кількість коней за ціною $y_{i}$ y_i за коня.

Мансур хоче дізнатись, яку максимальну суму грошей він міг би заробити, продаючи коней у найвигідніші моменти за $n$ років. Вас було запрошено в гості на той (святкове зібрання), і він просить вас відповісти на це питання.

Іноді Мансур згадує подробиці, які формують послідовність із $m$ уточнень. Кожне уточнення стосується одного з елементів $x_{i}$ x_i або $y_{i}$ y_i. Після кожного уточнення він знову просить порахувати, яку максимальну суму грошей він міг би заробити, продаючи коней. Уточнення застосовуються послідовно, тому для кожної відповіді необхідно враховувати всі попередні уточнення. Зверніть увагу: кожне значення $x_{i}$ x_i або $y_{i}$ y_i може оновлюватися більше одного разу.

Відповіді Мансура можуть бути дуже великими числами. Щоб уникнути операцій з величезними числами, необхідно виводити відповідь по модулю $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

У першому рядку вказано число минулих років $n$ ( $1 \leq n \leq 500000$ 1 \le n \le 500000). У другому рядку задано коефіцієнти приросту $x_{0}, x_{1}, \dots, x_{n - 1}$ x_0, x_1, \ldots, x_{n-1} наприкінці $i$ -го року ( $0 \leq i \leq n - 1$ 0 \le i \le n - 1), у третьому — ціни $y_{0}, y_{1}, \dots, y_{n - 1}$ y_0, y_1, \ldots, y_{n-1} за одного коня наприкінці $i$ -го року ( $0 \leq i \leq n - 1$ 0 \le i \le n - 1). Далі у наступному рядку подано кількість уточнень $m$ ( $1 \leq m \leq 1 0^{5}$ 1 \le m \le 10^5). Кожен із наступних $m$ рядків містить три числа type pos val (type $= 1$ для UpdateX, type $= 2$ для UpdateY, $0 \leq p os \leq n - 1$ 0 \le pos \le n - 1). І початкові, і нові значення масивів X та Y лежать у межах від $1$ до $1 0^{9}$ 10^9 включно.

Вихідні дані

Виведіть максимальну суму грошей (по модулю $1 0^{9} + 7$ 10^9 + 7), яку Мансур міг би заробити для початкових значень X і Y у першому рядку. Далі після кожного уточнення виводьте максимальну суму грошей (по модулю $1 0^{9} + 7$ 10^9 + 7), яку Мансур міг би заробити після застосування цього уточнення.

Приклади

Припустимо, минуло три роки ( $n = 3$ n = 3) й відомо таке:

За цих початкових значень Мансур заробить максимум, якщо продасть усіх коней наприкінці $1$ -го року. Його послідовність дій буде такою:

Спочатку у Мансура є один кінь.
Наприкінці $0$ -го року у нього буде два коні ( $1 \cdot X_{0} = 2$ 1 \cdot X_0 = 2).
Наприкінці $1$ -го року у нього все ще буде два коні ( $2 \cdot X_{1} = 2$ 2 \cdot X_1 = 2). Тепер він може їх продати і отримати прибуток $8$ ( $2 \cdot Y_{1} = 8$ 2 \cdot Y_1 = 8).

Після цього було одне уточнення ( $m = 1$ m = 1), і значення $y_{1}$ y_1 стало $2$ . Після уточнення ситуація така:

У цьому випадку один із оптимальних варіантів — продати одного коня наприкінці $0$ -го року, а трьох коней — наприкінці $2$ -го року. Послідовність дій:

Спочатку у Мансура є один кінь.
Наприкінці $0$ -го року у нього буде два коні ( $1 \cdot X_{0} = 2$ 1 \cdot X_0 = 2). Тепер можна продати одного, заробивши $3$ ( $1 \cdot Y_{0} = 3$ 1 \cdot Y_0 = 3). У нього залишиться один кінь.
Наприкінці $1$ -го року у нього буде один кінь ( $1 \cdot X_{1} = 1$ 1 \cdot X_1 = 1).
Наприкінці $2$ -го року у нього буде три коні ( $1 \cdot X_{2} = 3$ 1 \cdot X_2 = 3). Тепер він може їх продати й отримати $3$ ( $3 \cdot Y_{2} = 3$ 3 \cdot Y_2 = 3). Отже, максимальний сумарний прибуток — $6$ ( $3 + 3 = 6$ 3 + 3 = 6).

Приклад 1