众所周知，Rikka 不擅长数据结构。Yuta 很担心她的情况，于是给了她一些关于数据结构的练习题。这是其中之一：

Yuta 有一个包含 $n$ 个数字的数组 $A$，记作 $A[1], A[2], \dots, A[n]$。然后他会对数组进行 $m$ 次操作。

操作共有三种类型：

• 1 l r k：对于区间 $[l, r]$ 中的每个下标 $i$，将 $A[i]$ 的值修改为 $(A[i] + k)$；
• 2 l r k：对于区间 $[l, r]$ 中的每个下标 $i$，将 $A[i]$ 的值修改为 $k$；
• 3 l r x：Yuta 想让 Rikka 统计满足 $l \le y \le r$ 的不同下标 $y$ 的数量，使得 $\max\{A[\min\{x, y\}], A[\min\{x, y\} + 1], \dots, A[\max\{x, y\}]\} = \max\{A[x], A[y]\}$。

这对 Rikka 来说太难了。你能帮帮她吗？

输入格式

输入包含多组测试数据，第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $m$ ($1 \le m \le 10^5$)。

第二行包含 $n$ 个整数 $A[1], A[2], \dots, A[n]$ ($1 \le A[i] \le 10^9$)。

接下来 $m$ 行，每行描述一个操作，包含四个整数，如上所述，满足 $1 \le l \le r \le n$，$1 \le k \le 10^9$ 且 $1 \le x \le n$。

输入保证 $n > 10^3$ 或 $m > 10^3$ 的测试数据最多有 10 组。

输出格式

对于每个类型为 3 的查询操作，输出一行，包含一个整数，即该查询的答案。

样例

输入 1

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

输出 1

3
3
10
7
10
8
2