普二信的阿華 想要練習 bit (Fenwick Tree)，因為剛練習，先不做有變化的，請小西幫忙寫一個題目練習。

就是想練習以 Binary Index Tree 解 單點更新、區間求和, 可是又不想太因為 I/O 影響算法，所以讀入少許資料，跑個產生測資的小函式產生的測資放陣列

有N個正整數A[1...N], 5<N<=10^6, 0<A[i]<1000
有Q個指令，格式為 c x y， 分別放在陣列 C[1..Q]、X[1..Q]、Y[1..Q]， 5<Q<=10^5
其中 C[i] X[i] Y[i] 中的C[i]只有0及1 ， 1=<x,y<=N 如下說明：
0 x y 代表將 A[x]的值更新為 y，而 1 x y 代表要查詢 A[x]~A[y]的和{含A[x]及A[y]}

對於 1 x y 請輸出一列，只有一個數字 A[x]~A[y]的和 mod m 的值

 
=====================需加入 產生測資的部份 {小西只會C++}
const int MaxN = 1000000+5;
const int MaxQ = 100000+5;
int A[MaxN];
bool C[MaxQ];
int X[MaxQ] , Y[MaxQ];
int k,m,N,Q;
void gen_dat()
{
   int i,j;
   for( i=k+1; i<=max(Q,N); ++i )
        A[i] = ( A[i-2]*97 + A[i-1]*3 )%m+1;
   for(i=1,j=max(Q,N); i<=Q; ++i,--j)
  {
       C[i] = A[i]&1;
       X[i] = (A[i]+A[j])%N+1;
        if(C[i]) Y[i] = X[i]+ ( (A[i]<<3)+(A[j]<<5)+m )%( N-X[i]+1 );
       else Y[i] = ((A[i]<<3)+(A[j]<<5))%m+1;
   }
}
============================== 雖然有點醜，應該可以降低 I/O速率影響吧
以範例輸入的資料讀入後，呼叫 gen_dat()之後，產生的資料為
A[1..25]的值如下列
12 34 56 78 91 23 45 67 89 111 311 340 351 492 359 112 536 30 147 106 512 458 185 79 330
又產生的 15個指令 C[i] X[i] Y[i] 如以下15列，你需由陣列中叫用。
0 18 378
0 14 96
0 17 418
0 12 133
1 4 13
1 5 6
1 18 23
1 23 23
1 1 6
1 24 25
1 21 23
0 8 71
1 3 25
0 8 210
1 21 21
=========== 以上資料及指令的處理結果如下說明
第1~第4指令分別更新 A[18]=378、 A[14]=96、A[17]=418、A[12]=133， 更新後A陣列如下
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11][12][13] [14][15] [16] [17] [18] [19] [20] [21] [22]   [23] [24] [25]
12 34 56 78 91 23 45 67 89 111 311 133 351 96 359 112 418 378 147 106 512 458 185  79 330
接著第5個指令查 A[4]~A[13]的和，即 78 + 91 + 23 + 45 + 67 + 89 + 111 + 311 + 133 + 351 = 1299 再 mod 541 => 217
第6個指令查 A[5]~A[6]的和，即 91+23 = 114 、 第7查詢A[18]~A[23]的和，即 378+147+106+512+458+185 = 1786%541 => 163
... 第12個指令更新 A[8]=71 ， 接著 第13個查 A[3]~A[25]的和
56+78+91+23+45+71+89+111+311+133+351+96+359+112+418+378+147+106+512+458+185+79+330=4539再mod541 => 211
第14更新 A[8]=210 ， 接著 第15個查 A[21]~A[21]的和 為 512