Goļegs visu gadu gaidīja savu dzimšanas dienu, jo viņš grib dāvanas. Kad tā beidzot pienāca, viņam uzdāvināja masīvu a, kas sastāv no n naturāliem skaitļiem.

Segmentu, kas sākas pozīcijā l un beidzas pozīcijā r apzīmēsim ar (l,r). Tas atbilst masīva vērtībām a[l], a[l+1], ..., a[r].

Segmentu sauksim par garu, ja tā garums ir vismaz 2.

Divus segmentus (l1,r1) un (l2,r2) sauksim par līdzīgiem, ja to garumi vienādi, tie abi ir gari un ir kāds vesels skaitlis k, ar kuru a[l1+i]+k == a[l2+i] ar katru 0<=i<=r1-l1. Citiem vārdiem sakot, katrs pirmā segmenta elements atšķiras no attiecīgā otrā segmenta elementa par vienu un to pašu vērtību - k.

Goļegs par savu dāvanu kļuva ļoti dusmīgs, tāpēc viņš sāka bļaut. Viņš bļāva q reizes. Katra bļāviena pirmais lamuvārds ir skaitlis t.

Ja t = 1, tad tam seko lamuvārdi l, r, x. Goļega draugi izdomāja, ka viņš ar to bija domājis, lai masīva segmenta (l,r) katrai vērtībai pieskaita skaitli x.

Ja t = 2, tad tam seko lamuvārdi l, r. Tas nozīmē to, ka Goļegs izvēlas maksimāli daudz segmentu tā, ka (l,r) ir līdzīgs ar katru no izvēlētajiem segmentiem(li,ri) un nav tādu divu segmentu no izvēlētajiem, kas pārklātos. Jāņem vērā, ka Goļegs var izvēlēties arī doto segmentu (l,r).

Tu un Goļega draugi grib, lai Goļegs ātrāk nomierinātos un beigtu bļaut, tāpēc tev ir jāuzraksta programma, kas izpildīs aba veida bļāvienus.

Pirmajā rindā ir dots skaitlis n(2<=n<=5000) - masīva elementu skaits.

Nākamajā rindā doti n skaitļi a(-10^13<=a<=10^13).

Trešajā rindā ir skaitlis q(2<=q<=5000).

Katrā nākamajā rindā ir skaitlis t.
Ja t=1, tad tajā pašā rindā ir doti skaitļi l,r,x.(1<=l<=r<=n),(-10^13<=x<=10^13).
Ja t=2, tad tajā pašā rindā ir doti skaitļi l,r.(1<=l<r<=n).

Katrā rindiņā jāizvada atbilde uz bļāvieniem ar tipu t=2.
Ir garantēts, ka ir vismaz viens bļāviens ar tipu t=2.

Pirmajā testa piemērā segments (3,4) ir līdzīgs ar segmentiem (1,2),(3,4),(5,6), tāpēc atbildē ir šie visi segmenti, jo tie nepārklājas. Tad masīva segmentam (3,4) pieskaita 2 un tas kļūst par (1,2,3,4,5,6), un šoreiz segments (2,3) ir līdzīgs ar visiem segmentiem garumā 2, tāpēc tiek izvēlēti pēc iespējas vairāk segmentu: (1,2),(3,4),(5,6).

Otrajā testa piemērā pēc masīva pārveidošanas tiek izvēlēti segmenti (1,3) un (5,7).

Trešajā testā pirmajā bļāvienā tiek izvēlēti segmenti (1,2) un (3,4), bet otrajā bļāvienā segments (1,3).

30 punkti ja 2<=n,q<=300.

70 punkti, ja 2<=n,q<=5000.