P15897 [HackerEarth] 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
普及-
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
182 128 1000000 658151 951566 649338 519880 337186 655207 270461 88048 584812 331696 875789 69870 997515 82743 774048 564633 994891 616261 461243 462252 621173 134859 937075 906538 537434 746514 245541 191058 513214 65674 367937 687716 17239 17274 207595 870776 672481 994408 958824 773644 326103 350964 359866 839969 433706 133913 404602 944949 266525 382196 923552 404049 33406 376978 310587 570839 123491 72479 761896 636704 654505 646184 840771 188095 663458 564718 58871 852290 559125 17694 625933 401579 885009 502150 241548 318714 152414 162501 780014 418938 544696 703566 822987 94453 80543 649925 665291 204034 238755 943538 357089 893259 589721 197860 81354 769530 762577 140224 621819 838053 674269 764104 239631 559277 782605 997530 394342 935019 676382 690708 870308 737429 394273 209646 831881 991167 859570 13523 711552 614677 473412 584993 507935 63133 782852 105640 349014 61780 762215 970833 416184 952835 251288 172166 512111 33892 686048 422805 968910 362429 629864 839218 99858 24136 48863 448090 531654 424785 461613 243206 39461 935024 828198 63747 514508 127401 169387 863522 705532 447953 350706 638067 400788 601993 810232 429250 635884 12631 368406 604794 375060 998269 960363 991269 538756 525577 439358 70410 466713 417322 829967 506173 2 100 116 1 56 772010 2 97 138 1 29 620749 1 122 566351 1 83 934756 2 120 122 1 69 458159 1 87 480683 2 58 116 2 113 154 1 29 150381 1 151 18391 1 171 7546 2 49 75 1 160 948508 1 47 923018 1 5 403701 2 63 92 2 175 177 2 122 175 2 26 148 1 69 536920 2 90 107 2 155 179 1 48 846054 2 42 100 1 162 834654 2 144 170 2 180 181 1 105 334540 1 12 238007 1 30 94654 2 44 168 1 164 51256 1 19 641392 2 94 124 2 155 156 2 140 161 1 4 654720 1 171 335210 2 110 137 2 158 159 2 119 172 2 6 14 2 111 139 2 25 117 2 28 180 2 16 40 2 180 182 1 151 504188 2 175 178 1 161 227272 1 28 983360 1 38 430852 1 138 830947 2 31 132 1 138 876025 2 147 178 2 15 19 2 96 176 2 18 159 1 82 632560 2 86 129 2 101 148 2 171 176 1 91 508736 1 173 141295 2 130 153 1 100 240154 2 89 107 1 17 401422 1 17 987602 1 71 973105 2 119 142 1 139 999197 1 86 885620 1 78 493490 2 169 176 2 51 132 2 79 89 2 131 166 1 172 523511 2 98 122 2 113 144 1 4 108518 1 28 951216 2 109 162 2 157 160 1 42 567897 2 44 104 2 33 182 1 2 316661 2 169 176 1 33 592707 2 30 123 2 122 179 2 55 165 1 133 46396 2 32 103 1 12 749748 1 154 978287 1 35 850614 1 129 932043 1 161 124451 1 114 372260 2 121 158 1 109 285622 1 59 332017 2 144 155 1 72 537526 1 128 839658 2 137 156 1 64 180500 1 178 552759 2 116 175 1 54 198725 2 52 85 1 13 159850 1 18 117344 1 144 654869 1 143 10879 2 97 181 2 102 176 1 94 510387 2 140 173 2 113 165 2 180 181
样例输出
28251000 930476230 935792772