AT_abc440_f [ABC440F] Egoism

> AtCoder 牧場では馬がみずから水浴びをします。後片づけをする馬もいれば、散らかしたままにする馬もいます。 $ N $ 頭の馬がおり、 $ 1 $ から $ N $ までの番号が付けられています。馬 $ i $ ( $ 1 \leq i \leq N $ ) は**機嫌** $ A_i $ と**丁寧さ** $ B_i $ をもちます(ここで、 $ B_i $ は $ 1, 2 $ のいずれか)。 夜になると、 $ N $ 頭の馬が $ 1 $ 回ずつ水浴びをします。 $ j $ 回目 ( $ 1 \leq j \leq N $ ) に水浴びをする馬の番号を $ p_j $ とおくと、馬 $ p_j $ の**満足度**が以下で与えられます。 - $ j \geq 2 $ の場合、馬 $ p_j $ の機嫌と馬 $ p_{j-1} $ の丁寧さの積。 - $ j = 1 $ の場合、馬 $ p_j $ の機嫌。 これから $ Q $ 日にわたって毎日 $ 1 $ つずつクエリが与えられるので、順に処理してください。 $ k $ 日目 ( $ 1 \leq k \leq Q $ ) のクエリは以下の通りです。 - 馬 $ W_k $ の機嫌を $ X_k $ に、丁寧さを $ Y_k $ に変更する(ここで、 $ Y_k $ は $ 1, 2 $ のいずれか)。その後、その夜に $ N $ 頭の馬が水浴びをする順番を任意に決められるとき、その夜の $ N $ 頭の水浴びの満足度の総和が最大でいくらになるかを求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $ $ W_1 $ $ X_1 $ $ Y_1 $ $ \vdots $ $ W_Q $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ k $ 行目 ( $ 1 \leq k \leq Q $ ) には $ k $ 日目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 日目のクエリにおいて、馬 $ 3,1,4,2 $ の順に水浴びすることで、各馬の満足度は以下のようになります。 - 馬 $ 3 $ の満足度は $ 3 $ - 馬 $ 1 $ の満足度は $ 1 \times 1 = 1 $ - 馬 $ 4 $ の満足度は $ 7 \times 2 = 14 $ - 馬 $ 2 $ の満足度は $ 7 \times 2 = 14 $ このときの満足度の総和は $ 32 $ です。 $ 2 $ 日目のクエリにおいて、馬 $ 4,2,1,3 $ の順に水浴びすることで、各馬の満足度は以下のようになります。 - 馬 $ 4 $ の満足度は $ 7 $ - 馬 $ 2 $ の満足度は $ 7 \times 2 = 14 $ - 馬 $ 1 $ の満足度は $ 3 \times 1 = 3 $ - 馬 $ 3 $ の満足度は $ 3 \times 1 = 3 $ このときの満足度の総和は $ 27 $ です。 $ 3 $ 日目のクエリにおいて、馬 $ 4,3,2,1 $ の順に水浴びすることで、満足度の総和は $ 18 $ になります。 $ 4 $ 日目のクエリにおいて、馬 $ 4,3,1,2 $ の順に水浴びすることで、満足度の総和は $ 2000015 $ になります。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^6 $ ( $ 1 \leq i \leq N $ ) - $ B_i $ は $ 1,2 $ のいずれか ( $ 1 \leq i \leq N $ ) - $ 1 \leq W_k \leq N $ ( $ 1 \leq k \leq Q $ ) - $ 1 \leq X_k \leq 10^6 $ ( $ 1 \leq k \leq Q $ ) - $ Y_k $ は $ 1,2 $ のいずれか ( $ 1 \leq k \leq Q $ ) - 入力される値はすべて整数