FIBONACCI COFFECIENTS

3.6

19 votes
Very-Easy
Problem

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 (Ri=LA[i]F[iL])%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

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?