2098 - ログインボーナス

問題

イヅア国では、国民への情報提供サービスをするWebサイトを$N$日間運営している。このWebサイトの利用を促すため、イヅア国はログイン日数、および連続してログインした日数に連動したボーナスを、利用者に配布しようとしている。

ある国民が受け取るボーナスを計算する際には、ボーナスポイントの数値を決める0以上の整数を要素に持つ長さ$N$の数列$A=(A_1,A_2,...,A_N)$と$B=(B_1,B_2,...,B_N)$、その国民のログイン情報を示す0または1を要素に持つ長さ$N$の数列$S=(S_1,S_2,...,S_N)$が使われる。これらの数列を使って、開始日$l$から終了日$r$（ただし$1 \leq l \leq r \leq N$）までに、その国民が得られるボーナスが計算される。このとき、ボーナス$P(l,r)$は以下のようにして計算する。

$P(l,r)=g(l,l)+g(l,l+1)+⋯+g(l,r-1)+g(l,r)$

ただし、

$g(l,i)= (A_i+B_i \times f(l,i)) \times S_i$

ここで、$f(l,i)$は$S_i=0$のときは$0$で、そうでないときは次の２つの条件を満たす最大の整数tである。

• $l \leq i-t+1$。
• $S$の$i-t+1$番目の要素から$i$番目の要素までの値がすべて$1$。

あなたは、ボーナスポイントを計算する仕組みが正しく機能するかを確かめるように依頼された。このため、３つの要素$(c,l,r)$を持つ$Q$個のクエリを処理するプログラムを作成している。このクエリは以下の操作を示す。

• $c=1$のとき：$S$の$l$番目から$r$番目までの値を反転させる。つまり、元の値が0なら1、1なら0とする。
• $c=2$のとき：ボーナス$P(l,r)$を計算し、出力する。

あなたは効率的にクエリを処理するプログラムを作ることはできるだろうか。

数列$A$、$B$、$S$が与えられたとき、$Q$個のクエリを処理するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $Q$
$A_1$ $A_2$ ... $A_N$
$B_1$ $B_2$ ... $B_N$
$S_1$ $S_2$ ... $S_N$
$c_1$ $l_1$ $r_1$
$c_2$ $l_2$ $r_2$
:
$c_Q$ $l_Q$ $r_Q$

１行目に数列の長さ$N$ ($1 \leq N \leq 100,000=10^5$) と、クエリの個数$Q$ ($1 \leq Q \leq 100,000=10^5$)が与えられる。続く１行に数列$A$の各要素$A_i$ ($0 \leq A_i \leq 10,000,000=10^7$)が$N$個与えられる。続く１行に数列$B$の各要素$B_i$ ($0 \leq B_i \leq 10,000,000=10^7$)が$N$個与えられる。続く１行に数列$S$の各要素$S_i$ ($S_i=0$または$1$)が$N$個与えられる。続く$Q$行に$i$番目のクエリの操作$c_i$ ($c_i=1$または$2$)、$l_i$、$r_i$ ($1 \leq l_i \leq r_i \leq N$)が１行ずつ与えられる。ただし、操作が2であるクエリが1つ以上与えられる。

出力

クエリを順に処理し、操作が2であるクエリに対する答えを1行ずつ出力する。

入出力例

入力例

5 5
1 2 3 4 5
5 4 3 2 1
0 0 1 1 1
2 1 5
1 1 4
2 1 5
2 2 5
2 3 4

出力例

22
22
12
0