Hide

Problem F
Fibonacci Gjöf

Languages en is

Siggi litli fékk fylki af n jákvæðum heiltölum, x1,x2,,xn, í afmælisgjöf frá ömmu sinni. Þessar heiltölur eru ekki bara einhverjar heiltölur, heldur tákna þær númer á Fibonacci tölum. Fibonacci tala númer 1 er 1, Fibonacci tala númer 2 er líka 1, og svo er næsta Fibonacci tala alltaf reiknuð með því að leggja saman síðustu tvær Fibonacci tölur. Fibonacci tala númer 3 er því 1+1=2, Fibonacci tala númer 4 er 1+2=3, Fibonacci tala númer 5 er 2+3=5, og svo koll af kolli. Við táknum Fibonacci tölu númer n sem Fib(n).

Hann Siggi litli er að leika sér með nýja fylkið sitt, en honum finnst gaman að gera eftirfarandi tvær aðgerðir við fylkið:

  1. Siggi velur sér jákvæða heiltölu d og eitthvað bil í fylkinu sem byrjar í l og endar í r, þ.e. xl,xl+1,,xr. Hann bætir svo heiltölunni d við öll stökin í fylkinu á þessu bili.

  2. Siggi velur sér eitthvað bil í fylkinu sem byrjar í l og endar í r, og reiknar summuna af öllum þeim Fibonacci tölum sem heiltölurnar á þessu bili tákna:

    Fib(xl)+Fib(xl+1)++Fib(xr)

Nú er hann orðinn svolítið leiður á að gera þetta í höndunum, og biður þig því um aðstoð. Gefið upphaflega fylkið sem Siggi litli fékk í afmælisgjöf, og þær aðgerðir sem Siggi litli framkvæmir, getur þú reiknað svarið fyrir hverja aðgerð nr. 2 sem Siggi litli framkvæmir?

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur n og m (1n,m105), stærðin á fylkinu hans Sigga litla og fjöldi aðgerða sem hann framkvæmir.

Næsta lína inniheldur n heiltölur x1,x2,,xn aðskildar með bili, sem tákna fylkið sem Siggi litli fékk í afmælisgjöf (1xi109 fyrir öll i).

Síðan koma m línur, ein fyrir hverja aðgerð sem Siggi framkvæmir, en hver þeirra er á öðru hvoru af eftirfarandi formum:

  • 1 l r d: Siggi litli framkvæmir aðgerð nr. 1 með töluna d á bilið l, r. (1lrn, 1d109)

  • 2 l r: Siggi litli framkvæmir aðgerð nr. 2 á bilið l, r. (1lrn)

Úttak

Fyrir hverja aðgerð nr. 2, skrifið út eina línu með gildinu á summunni sem Siggi litli reiknar. Þessi tala getur orðið svolítið stór, og biðjum við því ykkur um að skrifa út afganginn af svarinu þegar honum er deilt með 109+7.

Stigagjöf

Hópur

Stig

Takmarkanir

1

22

n100, m32, d=1, xi=1

2

26

n1000, m100, d=1, xi=1

3

25

n1000, m100

4

27

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
4 5
1 1 1 1
2 2 3
1 1 2 2
2 2 3
1 2 2 4
2 1 4
2
3
17
Sample Input 2 Sample Output 2
5 6
10 7 3 5 4
2 1 1
2 2 3
2 4 5
1 1 3 20
1 3 5 100
2 1 5
55
15
8
403785010
Hide

Please log in to submit a solution to this problem

Log in