AT_abc368_g [ABC368G] Add and Multiply Queries

[problemUrl]: https://atcoder.jp/contests/abc368/tasks/abc368_g 長さ $ N $ の正整数列 $ A,\ B $ が与えられます。以下の形式で与えられる $ Q $ 個のクエリを、与えられた順番に処理してください。クエリは次の $ 3 $ 種類のいずれかです。 - タイプ $ 1 $ : `1 i x` の形式で与えられる。$ A_i $ を $ x $ に置き換える。 - タイプ $ 2 $ : `2 i x` の形式で与えられる。$ B_i $ を $ x $ に置き換える。 - タイプ $ 3 $ : `3 l r` の形式で与えられる。以下の問題を解き、答えを出力する。 - はじめ $ v\ =\ 0 $ とする。$ i\ =\ l,\ l\ +\ 1,\ \dots\ ,r $ の順に、 $ v $ を $ v\ +\ A_i $ もしくは $ v\ \times\ B_i $ で置き換える操作を行う。最終的な $ v $ として実現できる最大値を求めよ。 ただし、**入力で与えられるタイプ $ 3 $ のクエリの答えは $ 10^{18} $ 以下であることが保証されています。**

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ Q $ $ query_1 $ $ query_2 $ $ \vdots $ $ query_Q $ ここで $ query_i $ は $ i $ 番目のクエリであり、以下のいずれかの形式で与えられる。 > $ 1 $ $ i $ $ x $ > $ 2 $ $ i $ $ x $ > $ 3 $ $ l $ $ r $

タイプ $ 3 $ のクエリの個数を $ q $ 個として、 $ q $ 行出力せよ。$ i $ 行目には $ i $ 番目のタイプ $ 3 $ のクエリの答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ B_i\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - タイプ $ 1 $, $ 2 $ のクエリにおいて、 $ 1\ \leq\ i\ \leq\ N $ - タイプ $ 1 $, $ 2 $ のクエリにおいて、 $ 1\ \leq\ x\ \leq\ 10^9 $ - タイプ $ 3 $ のクエリにおいて、 $ 1\ \leq\ l\ \leq\ r\ \leq\ N $ - タイプ $ 3 $ のクエリにおいて、出力すべき値は $ 10^{18} $ 以下である ### Sample Explanation 1 $ 1 $ 番目のクエリでは、答えは $ ((0\ +\ A_1)\ \times\ B_2)\ \times\ B_3\ =\ 12 $ です。 $ 3 $ 番目のクエリでは、答えは $ ((0\ +\ A_1)\ +\ A_2)\ +\ A_3\ =\ 7 $ です。