题目描述

给定一个长度为 \(n\) 的数组 \(A\)，你需要实现一个数据结构来维护该数组，并支持以下两种操作：

• 1 L R X：将区间 \([L, R]\) 内的所有元素执行减 \(X\) 操作（即 \(A_{i} = A_i-X\)，其中 \(L \le i \le R\)）。
• 2 L R：将区间 \([L, R]\) 内的所有元素整体右移一位（即 \(A_i = A_i\gg 1\)，其中 \(L \le i \le R\)）。

此外，还存在有一个阈值 \(m\)，当整个数组中存在至少一个元素小于等于 \(m\) 时，会触发时空回溯：

• 全局重置次数 \(k\) 增加 1；
• 整个数组立即恢复为最初的初始状态。

请你在处理完所有给定操作后，输出最终的 \(k\) 值。

输入格式

第一行一个正整数 \(T\) 表示数据组数。

对于每组数据：

输入的第一行包含三个整数 \(n, m\) 和 \(Q\)，分别表示数组长度，阈值大小和操作次数。

第二行包含 \(n\) 个整数，表示数组的初始值 \(A_1, A_2, \dots, A_N\)。

接下来 \(Q\) 行，每行表示一个操作：

• 若为操作 \(1\)，格式为 1 L R X；
• 若为操作 \(2\)，格式为 2 L R.

\(1 \le T \le 10\)

对于每组测试数据：

\(1 \le n \le 10^5, 0 \le m < 2^{30}, 1 \le Q \le 10^5, m < A_i < 2^{30}\)

对于操作 \(1\)： \(1 \le L \le R \le n, 0 \le X < 2^{30}\)

对于操作 \(2\)： \(1 \le L \le R \le n\)

输出格式

对于每组测试数据，输出一个整数，表示最终的重置次数 \(k\)。

样例输入

1
3 1 3
5 4 6
1 1 2 4
2 2 3
1 1 3 5

样例输出

2

提示

初始数组为 \([5, 4, 6]\)。

第 \(1\) 次操作：数组变为 \([1, 0, 6]\)。存在元素 \(\le m\)，触发回溯， \(cnt = 1\)，数组重置为 \([5, 4, 6]\)。

第 \(2\) 次操作：数组变为 \([5, 2, 3]\)。

第 \(3\) 次操作：数组变为 \([0, -3, -2]\)。存在元素 \(\le m\)，触发回溯， \(cnt = 2\)，数组重置为 \([5, 4, 6]\)。