Optimized Array Operations

You are given an array \(a_1, a_2, \ldots, a_n\) and an integer \(p\). You need to perform a series of \(q\) operations on the array. There are two types of operations:

• Operation1(l, r, c): For every index \(i\) with \(l \le i \le r\), update \(a_i\) as \(a_i = (a_i + c) \bmod p\).
• Operation2(l, r): Count the number of indices \(i\) with \(l \le i a_{i+1}\) and output the count.

You are given the initial array and a sequence of operations, and your task is to return the outputs produced by every Operation2.

inputFormat

The first line contains three integers \(n\), \(p\), and \(q\) where \(n\) is the size of the array, \(p\) is the modulus, and \(q\) is the number of operations.

The second line contains \(n\) integers representing the initial values of the array \(a_1, a_2, \ldots, a_n\).

Each of the following \(q\) lines represents an operation in one of the following formats:

• 1 l r c: Representing Operation1.
• 2 l r: Representing Operation2.

outputFormat

For each Operation2 query, output the corresponding count on a separate line.

sample

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

2