問題 フィボナッチ数のi番目をF[i]とする。 長さnの数列a[i]が与えられる。次のようなクエリがq個来るので処理せよ。 1 l r : l≦i≦rなるiに対してa[i]:=a[i] + F[i-l+1]と更新する 2 l r : l≦i≦rなるiに対してa[i]の和をmod 10^9 + 9で出力する。 制約条件 n,…