给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。

定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\le x< j$ 且 $a_x\neq a_{x+1}$。

有 $m$ 次操作：

1 l r x：表示将区间 $[l,r]$ 中所有元素都修改为 $x$。

2 l r x：表示查询区间 $[l,r]$ 中，对任意 $l\le i< j\le r$，且 $a_i=a_j=x$，$f(i,j)$ 的和。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行四个用空格隔开的数 $opt,l,r,x$ 表示一次操作。

输出格式

对每个 $2$ 操作，输出一行一个数表示答案。

样例数据

样例输入

10 10
2 1 2 1 8 3 2 1 2 2
2 6 9 2
2 3 10 2
2 2 10 2
2 1 3 2
2 4 10 1
1 2 4 2
2 3 10 2
2 2 7 1
2 2 7 2
2 3 6 2

样例输出

2
20
20
2
4
30
0
9
0

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078

对于 $20\%$ 的数据，满足 $1\le n,m\le 1000$。

对于另外 $20\%$ 的数据，没有 $1$ 操作。

对于另外 $10\%$ 的数据，数据中的操作类型在 $[1,2]$ 内， $a_i,x$ 在 $[1,100]$ 内均匀随机生成，区间 $[l,r]$ 两个端点为 $[1,n]$ 中均匀随机生成的整数，如果生成后 $l>r$，则将二者交换。

对于另外 $30\%$ 的数据，满足 $1\le n,m\le 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m \le 5\times10^5$，$1\le l\le r\le n$，$1\le a_i,x\le n$，所有输入均为整数。