D. Хүүхэд ба дараалал

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

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

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

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

Хүүхдүүдийн өдрөөр хүүхэд Пикийн гэрт ирсэн ба түүний гэр заваарсан. Пик үүнд их уурласан байна. Их олон чухал зүйлс алдагдсан, ялангуяа түүний дуртай дараалал.

Аз болоход Пик дарааллыг хэрхэн сэргээхийг санаж байна. Эхлээд $a[1], a[2], ..., a[n]$ бүхэл тоон массивыг үүсгэх ёстой. Дараа нь тэр $m$ үйлдлүүдийн дараалал гүйцэтгэнэ. Үйлдэл нь дараахаас аль нэг нь байна:

  1. $l, r$ үйлдлийг хэвлэнэ. Пик утгыг доош нь бичих ёстой.
  2. $l, r, x$ модуль үйлдэл. $i$ $(l ≤ i ≤ r)$ бүрийн хувьд Пик $a[i] = a[i] mod x$ үйлдлийг гүйцэтгэх ёстой.
  3. $k, x$ тохируулах үйлдэл. Пик $a[k]$-н утгыг $x$-д тохируулах ёстой (өөрөөр хэлвэл $a[k] = x$ үйлдлтийг гүйцэтгэнэ).

Үйлдлүүдийн бүх дарааллыг гүйцэтгэхэд Пикд тусалж чадах уу?

Оролт

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

Дараагийн $m$ мөр бүр нь $type$ тоогоор эхэлдэг .

  • Хэрвээ $type = 1$ бол мөрөнд хоёр бүхэл тоо байна: $l, r (1 ≤ l ≤ r ≤ n)$, үйлдэл 1-тэй тохирно.
  • Хэрвээ $type = 2$ бол мөрөнд 3 бүхэл тоо байна: $l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 10^{9})$, үйлдэл 2-той тохирно.
  • Хэрвээ $type = 3$ бол мөрөнд хоёр бүхэл тоо байна: $k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 10^{9})$, үйлдэл 3-тай тохирно.

Гаралт

Үйлдэл 1 бүрийн хариуг агуулсан мөр хэвлэнэ. Хариу 32-битийн бүхэл тоог давж болно гэдгийг анхаараарай.

Орчуулсан: Даариймаа

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

Оролт
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3
Гаралт
8
5
Оролт
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10
Гаралт
49
15
23
1
9

Тэмдэглэл

Эхний жишээг авч үзье:

  • Эхлээд, $a = {1, 2, 3, 4, 5}$.
  • Дараагийн үйлдэл $1$, $a = {1, 2, 3, 0, 1}$.
  • Дараагийн үйлдэл $2$, $a = {1, 2, 5, 0, 1}$.
  • Үйлдэл $3$, $2 + 5 + 0 + 1 = 8$.
  • Дараагийн үйлдэл $4$, $a = {1, 2, 2, 0, 1}$.
  • Үйлдэл $5$, $1 + 2 + 2 = 5$.
Сэтгэгдлүүдийг ачааллаж байна...