Range Update and Query

You are given a sequence of length ( n ), denoted as ({a_i}), with initial values. You need to perform ( m ) operations on this sequence. There are three types of operations:

1. Operation (1\ t\ g\ c): For all indices ( i ) satisfying ( t \leq i \leq g ), update ( a_i = a_i \times c ).
2. Operation (2\ t\ g\ c): For all indices ( i ) satisfying ( t \leq i \leq g ), update ( a_i = a_i + c ).
3. Operation (3\ t\ g): Compute the sum ( S = \sum_{i=t}^{g} a_i ) and output ( S \mod p ).

Each operation is applied sequentially. Note that the modulus ( p ) only applies to the output of the query operations (type 3), not during the update operations.

inputFormat

The first line of input contains three integers: ( n ) (the length of the sequence), ( m ) (the number of operations), and ( p ) (the modulus). The second line contains ( n ) integers: ( a_1, a_2, \ldots, a_n ), representing the initial sequence. Each of the next ( m ) lines describes an operation in one of the following formats:

• 1 t g c: Multiply every \( a_i \) (for \( t \leq i \leq g \)) by \( c \).
• 2 t g c: Add \( c \) to every \( a_i \) (for \( t \leq i \leq g \)).
• 3 t g: Output the sum of \( a_t, a_{t+1}, \ldots, a_g \) modulo \( p \).

outputFormat

For each operation of type 3, output a single line containing the result, which is the sum of the specified subarray modulo ( p ).

sample

5 5 100
1 2 3 4 5
3 1 5
1 2 4 2
3 1 5
2 3 5 3
3 1 5

15
24
33