Array Processor Queries

You are given an array of n integers and a modulus value m. You will also be given q queries. There are two types of queries:

• Type 1: Query the sum of a subarray. The query is given as: 1 L R. You must compute the value \(\displaystyle S = \sum_{i=L}^{R} a_i\) and output \(S \bmod m\).
• Type 2: Update an element of the array. The query is given as: 2 index value. Replace the element at position index with value.

All queries are provided in order. For each Type 1 query, output the result on a new line.

Note: The array is 1-indexed. It is guaranteed that the input format is valid.

inputFormat

The first line contains three integers n, q, and m where n is the number of elements in the array, q is the number of queries, and m is the modulus value.

The second line contains n space-separated integers representing the array.

The following q lines each contain a query in one of the following formats:

• 1 L R for a range sum query.
• 2 index value for an update query.

outputFormat

For each Type 1 query, output a single line containing the result which is the sum of the subarray from L to R modulo m.

## sample

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

7
5
5

</p>