問題文

各要素が $0,1,2$ のいずれかである長さ $N$ の数列 $A=(A_1,\\ldots,A_N)$ が与えられます。
$Q$ 個のクエリを順に処理してください。各クエリは以下の $2$ 種類のいずれかです。

• 1 L R：数列 $(A_L,\\ldots,A_R)$ の転倒数を出力する
• 2 L R S T U： $L\\leq i \\leq R$ を満たす各 $i$ について、$A_i$ が $0$ なら $S$ に、$1$ なら $T$ に、$2$ なら $U$ に置き換える

転倒数とは？ 数列 $B = (B_1, \\ldots, B_M)$ の転倒数とは、整数の組 $(i, j)$ $(1 \\leq i < j \\leq M)$ であって $B_i > B_j$ を満たすものの個数です。

制約

• $1 \\leq N \\leq 10^5$
• $0 \\leq A_i \\leq 2$
• $1\\leq Q\\leq 10^5$
• 各クエリにおいて、$1\\leq L \\leq R \\leq N$
• $2$ 種類目のクエリにおいて、$0\\leq S,T,U \\leq 2$
• 入力に含まれる値は全て整数である

入力

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

$N$ $Q$ $A_1$ $A_2$ $\\ldots$ $A_N$ $\\rm Query_1$ $\\rm Query_2$ $\\vdots$ $\\rm Query_Q$

ここで $i$ 番目のクエリを表す $\\rm Query_i$ は以下のいずれかの形式で与えられる。

$1$ $L$ $R$ $2$ $L$ $R$ $S$ $T$ $U$

出力

$1$ 種類目のクエリに対する答えを順に改行区切りで出力せよ。

入力例 1

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

出力例 1

3
4

最初 $A=(2,0,2,1,0)$ です。

• $1$ 番目のクエリにおいて、$(A_2,A_3,A_4,A_5)=(0,2,1,0)$ の転倒数 $3$ を出力します。
• $2$ 番目のクエリを処理すると、$A=(2,2,0,1,0)$ となります。
• $3$ 番目のクエリにおいて、$(A_2,A_3,A_4,A_5)=(2,0,1,0)$ の転倒数 $4$ を出力します。

入力例 2

3 3
0 1 2
1 1 1
2 1 3 0 0 0
1 1 3

出力例 2

0
0