3-н настай Ухаалаг Минж бүх арифметикийн үйлдлийг гаргууд эзэмшсэн ба гайхширсан багшаасаа уг зуны даалгаврыг авчээ:

Танд бүхэл тоонуудын $a_{1}, a_{2}, ..., a_{n}$ дараалал өгөгдөв. Та дараах төрлийн $m$ ширхэг дараалсан үйлдлийг уг дараалал дээр гүйцэтгэх юм:

1. өгөгдсөн $x_{i}$ болон $v_{i}$ тоонуудын хувьд $a_{x_{i}}$ элементийн утгыг $v_{i}$ болгоно.
2. өгөгдсөн $l_{i}$ болон $r_{i}$ тоонуудын хувьд та нийлбэрийг тооцох ба энд $f_{0} = f_{1} = 1$ бөгөөд $i ≥ 2$-ын хувьд $f_{i} = f_{i - 1} + f_{i - 2}$ байна.
3. $l_{i}$ $r_{i}$ $d_{i}$ гэсэн 3-н тооны хувьд бүх $x$ $(l_{i} ≤ x ≤ r_{i})$-ын хувьд $a_{x}$-ын утгыг $d_{i}$-аар нэмэгдүүлнэ.

Ухаалаг Минж Монгол улсын үзэсгэлэнт хөдөө орон нутгаар аялахаар төлөвлөсөн учраас танаас уг өгөгдсөн бодлогыг бодож өгөхийг хүсжээ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 2*10^{5}$) өгөгдөнө -- эдгээр нь харгалзан дараалал дахь бүхэл тоонуудын тоо болон хийх ёстой үйлдлүүдийн тоог илэрхийлнэ. 2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} ≤ 10^{5}$) өгөгдөнө. Дараагийн $m$ мөрийн мөр болгонд нэг үйлдлийг дүрсэлсэн байна. Мөр болгонд бүхэл тоо $t_{i}$ ($1 ≤ t_{i} ≤ 3$) өгөгдөнө -- энэ нь үйлдлийн төрлийг илэрхийлнэ:

• хэрэв $t_{i} = 1$ бол араас нь 2 бүхэл тоо $x_{i}$ $v_{i}$ ($1 ≤ x_{i} ≤ n, 0 ≤ v_{i} ≤ 10^{5}$) өгөгдөнө;
• хэрэв $t_{i} = 2$ бол араас нь 2 бүхэл тоо $l_{i}$ $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө;
• хэрэв $t_{i} = 3$ бол араас нь 3 бүхэл тоо $l_{i}$ $r_{i}$ $d_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n, 0 ≤ d_{i} ≤ 10^{5}$) өгөгдөнө.

$30$-н оноо авах оролтын хязгаар (дэд бодлого E1):

• $n$-н $100$-аас хэтрэхгүй, $m$-н $10000$-аас хэтрэхгүй ба $3$-дахь төрлийн үйлдэл байхгүй байна.

$70$-н оноо авах оролтын хязгаар (дэд бодлого E1+E2):

• зөвхөн $1$-дэх болон $2$-дахь төрлийн үйлдлүүд өгөгдөнө.

$100$-н оноо авах оролтын хязгаар (дэд бодлого E1+E2+E3):

• Ямар ч нэмэлт хязгаар байхгүй.

Гаралт

2-дахь төрлийн үйлдэл бүрийн хувьд нийлбэрийг $1000000000$ $(10^{9})$ модулаар бодон хэвлэнэ үү.