配点 : $600$ 点

問題文

各要素が $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$ に置き換える

制約

• $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$ 種類目のクエリに対する答えを順に改行区切りで出力せよ。

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

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$ を出力します。

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

0
0