题目描述

众所周知，Rikka 并不擅长数据结构。Yuta 对此感到担忧，于是他给 Rikka 布置了一些数据结构相关的练习任务。以下是其中之一：

Yuta 有一个包含 $n$ 个数的数组 $A$，记为 $A[1], A[2], \cdots, A[n]$。随后他在该数组上执行 $m$ 次操作。操作共有三种类型：

• $\text{1 l r k}$：对于每个满足 $i \in [l, r]$ 的下标 $i$，将 $A[i]$ 的值改为 $(A[i] + k)$；
• $\text{2 l r k}$：对于每个满足 $i \in [l, r]$ 的下标 $i$，将 $A[i]$ 的值改为 $k$；
• $\text{3 l r x}$：Yuta 想让 Rikka 统计满足 $l \le y \le r$ 且 $\max \lbrace A[\min \lbrace x, y \rbrace ], A[\min \lbrace x, y \rbrace +1], \cdots, A[\max \lbrace x, y \rbrace ] \rbrace = \max \lbrace A[x], A[y] \rbrace$ 的不同下标 $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], \cdots, 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$。

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

输出格式

对于每个类型为 $3$ 的询问操作，输出一行一个整数，表示该询问的答案。

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

3
3
10
7
10
8
2

提示

翻译由 DeepSeek V4 Pro 完成