fibonacci-coffecients

Getting bored was never an option for Debu. So to keep himself occupied Debu asked his brother Biswa to find the sum of elements in a subarray of an array. But then it was too boring to begin with and hence Biswa asked Debu to find the Fibo-sum of a subarray. 

But Debu was able to find the Fibo-sum of any subarray very easily so Biswa from time to time changed some element of the array to some other value and then continued asking him the Fibo-sum for different subarrays. 

A Fibo-sum is defined for he subarray [L, R] is defined as  ( \sum_{i = L}^{R}{A[i]*F[i-L]} ) \% Mod.

Here, F[0] = F[1] = 1 and F[i] = F[i - 1] + F[i - 2]
Input

 The first line contains 3 space seperated integers having N M Mod
 Next line contains a N space separated integers which are the values of the array
 Next M lines have queries. Each query is of one of the following type:

 1 L X: Change the value of array element at index L to X.
 2 L R   : Find the Fibo-sum of the subarray L to R .
Constraints:
1 ≤ N ≤ 200000

1 ≤ M ≤ 100000

L ≤ R

2 ≤ mod ≤ 1000000000

SAMPLE INPUT
5 5 10000000
1 1 1 1 1 
2 1 4
2 1 5
2 2 4
1 3 1
2 1 5

SAMPLE OUTPUT
7
12
4
12

Source: hackerearth | Difficulty: EASY


Solutions: