D. Зигзаг

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Шидтэн Зигзаг алдартай математикч болохыг хүсэж байна. Үүний тулд түүнд Каучийн теорем шиг өөрийн гэсэн теорем эсвэл Минковскийн нийлбэр шиг өөрийн гэсэн нийлбэр хэрэгтэй. Гэвч түүний хамгийн их хүсч байгаа зүйл нь Фибоначийн дараалал шиг өөрийн дараалал, Эйлерийн тотинтийн функц шиг өөрийн функцтэй болохыг хүсч байна.

z фактортой Зигзагийн дараалал нь хязгааргүй $S_{i}^{z}$ $(i ≥ 1; z ≥ 2)$ дараалал байх ба дараах байдлаар тодорхойлогдоно:

  • үед $S_{i}^{z} = 2$;
  • үед ;
  • үед .

үйлдэл нь $x$ тоог $y$ тоонд хуваагаад гарсан үлдэгдлийг авна гэсэн үг. Жишээлбэл $S_{i}^{3}$ (зигзаг фактор нь 3) дарааллын эхлэл нь: 1, 2, 3, 2, 1, 2, 3, 2, 1 байдалтай харагдана.

Бидэнд $n$ бүхэл тооноос бүрдэх $a$ массив өгөгдсөн гэе. Массивийн $i$ $(1 ≤ i ≤ n)$ дугаартай элементийг $a_{i}$ гэж тодорхойлье. Зигзаг функц нь функц ба энд $l, r, z$ нь $1 ≤ l ≤ r ≤ n$, $z ≥ 2$ тэнцэтгэл бишийг хангана.

Зигзаг дараалал болон Зигзаг функцтэй илүү танилцахын тулд шидтэн таныг өгөгдсөн $a$ массив дээр дараах үйлдлүүдийг хэрэгжүүлэхийг санал болгож байна.

  1. Оноох үйлдэл. Үйлдлийн параметрууд нь $(p, v)$ байна. Энэ үйлдэл нь массивийн $p$-р элементэд $v$ утгыг оноохыг заана. Үйлдэл гүйцэтгэгдсэний дараа массивийн $a_{p}$ элемент $v$-тэй тэнцүү байна.
  2. Зигзаг үйлдэл. Үйлдлийн параметрууд нь $(l, r, z)$ байна. Энэ үйлдэл нь $Z(l, r, z)$ Зигзаг функцийг тооцоолох үйлдэл юм.

Зигзагийн шидэт хүчийг нээ, тодорхойлогдсон үйлдлүүдийг гүйцэтгэ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5})$ байх ба $a$ массивийн элементүүдийн тоо юм. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$ байх буюу массивийн элементүүд юм.

Гурав дахь мөрөнд бүхэл тоо $m$ $(1 ≤ m ≤ 10^{5})$ байх ба үйлдүүдийн тоо юм. Дараагийн $m$ мөрөнд үйлдлүүдийн тайлбар байна. Үйлдлийн тайлбар үйлдлийн төрөл болох $t_{i}$ $(1 ≤ t_{i} ≤ 2)$ бүхэл тоогоор эхлэнэ.

  • Хэрвээ $t_{i} = 1$ (оноох үйлдэл) байвал уг мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $p_{i}, v_{i}$ $(1 ≤ p_{i} ≤ n; 1 ≤ v_{i} ≤ 10^{9})$ байх буюу оноох үйлдлийн параметрууд юм.
  • Хэрвээ $t_{i} = 2$ (Зигзаг үйлдэл) байвал уг мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоо $l_{i}, r_{i}, z_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n; 2 ≤ z_{i} ≤ 6)$ байх буюу оноох Зигзаг үйлдлийн параметрууд юм.

Та үйлдлүүдийг оролтонд өгсөн дарааллаар нь гүйцэтгэх ёстой.

Гаралт

Зигзаг үйлдэл бүрийн хувьд Зигзаг функцийн тооцоолсон утгыг нэг мөрөнд хэвлэ. Зигзаг функцийн утгуудыг оролтонд өгсөн дарааллаар нь хэвлэ.

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
2 3 1 5 5
4
2 2 3 2
2 1 5 3
1 3 5
2 1 5 3
Гаралт
5
26
38

Тэмдэглэл

Жишээ тестийн тайлбар:

  • Эхний үйлдлийн үр дүн $Z(2, 3, 2) = 3*1 + 1*2 = 5$.
  • Хоёрдугаар үйлдлийн үр дүн $Z(1, 5, 3) = 2*1 + 3*2 + 1*3 + 5*2 + 5*1 = 26$.
  • Гуравдугаар үйлдлийн дараа $a$ массив $2, 3, 5, 5, 5$ болно.
  • Дөрөвдүгээр үйлдлийн үр дүн $Z(1, 5, 3) = 2*1 + 3*2 + 5*3 + 5*2 + 5*1 = 38$ байна.
Сэтгэгдлүүдийг ачааллаж байна...