给定一个长度为 n 的序列。你需要支持一下两种操作。

- 操作一：将区间 [l,r] 中每个数加上 c，并对 P 取模。形式化的，
∀i∈[l,r], a[i] ← (a[i]+c) mod P。

- 操作二：询问区间 [l,r] 中，a[i]>a[i+1] 的个数。形式化的，求出 \sum_{i=l}^{r-1}[a_i> a_{i + 1}] 。

第一行三个正整数依次为 n,m,P 。

接下来一行 n 个整数表示序列 a 。

接下来 m 每行表示一个操作。如果是操作一，格式为 ``1 l r c``，如果是操作二，格式为 ``2 l r``。

对于每个操作二，输出一行一个整数表示答案。

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

2
1
3

数据规模
对于 100% 的测试点， 1≤n≤10^6, 1≤P≤10^9, 0≤a_i,c< P, 1≤l≤r≤n, 1≤m≤2n 。

本题共 20 个测试点，每个测试点 5 分。
对于测试点 1,2，n≤1000 。
对于测试点 3~6，c≤1, P≥5×10^5 。
对于测试点 7,8，l =1,r=n 。
对于测试点 9~12 ，对于所有操作一，l = 1,r=n 。
对于测试点 1~19 ，n≤10^5 。