题目描述

给定长度为 $N$ 的序列 $A=(A_1, A_2, \dots, A_N)$。每个元素都是 $0$, $1$ 或 $2$。
按顺序处理 $Q$ 个查询。每个查询有以下两种类型之一：

• 1 L R：输出序列 $(A_L, A_R)$ 的逆序数。
• 2 L R S T U：对于所有满足 $L\\leq i \\leq R$ 的 $i$，如果 $A_i=0$，则替换为 $S$；如果 $A_i=1$，则替换为 $T$；如果 $A_i=2$，则替换为 $U$。

什么是逆序数？序列 $B = (B_1, B_2, \dots, 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$。
• 在第二种查询中，$0 \\leq S, T, U \\leq 2$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

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

其中，$Query_i$ 表示第 $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

示例输出 1

3
4

初始时，$A=(2,0,2,1,0)$。

• 第一个查询，输出序列 $(A_2,A_3,A_4,A_5)=(0,2,1,0)$ 的逆序数 $3$。
• 第二个查询，将 $A$ 修改为 $(2,2,0,1,0)$。
• 第三个查询，输出序列 $(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