E. Ярослав ба цэгүүд

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

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

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

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

Ярославд $Ox$ тэнхлэг дээр орших $n$ цэг байгаа. Эхний цэгийн координат нь $x_{1}$, хоёр дахь цэгийн координат нь $x_{2}$ гэх мэтчилэн $n$-р цэгийн координат нь $x_{n}$ байна. Одоо Ярослав $m$ хүсэлт гүйцэтгэхийг хүссэн ба эдгээр нь тус бүрдээ дараах хоёр төрлийн аль нэг нь байна:

  1. $p_{j}$-р цэг нь $x_{p_{j}}$ байрлалаас $x_{p_{j}} + d_{j}$ байрлал руу шилжинэ. Хүсэлтийг гүйцэтгэсний дараа цэгүүдийн бүх координат нь ялгаатай байна гэдэг нь баталгаатай.
  2. $[l_{j}, r_{j}]$ $(l_{j} ≤ r_{j})$ завсар дахь бүх хос цэгүүдийн хоорондын зайн нийлбэрийг тоолно. Өөрөөр хэлбэл та энэ: нийлбэрийг тоолно.

Ярославд туслана уу.

Оролт

Эхний мөрөнд цэгүүдийн тоо болох $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог оруулна. Хоёр дахь мөрөнд ялгаатай бүхэл $x_{1}, x_{2}, ..., x_{n}$ $(|x_{i}| ≤ 10^{9})$ тоонууд агуулагдана. Эдгээр нь цэгүүдийн координатууд юм.

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

  • Хэрэв $t_{j} = 1$ бол бүхэл $p_{j}$ болон $d_{j}$ $(1 ≤ p_{j} ≤ n, |d_{j}| ≤ 1000)$ тоонуудыг оруулна.
  • Хэрэв $t_{j} = 2$ бол бүхэл $l_{j}$ болон $r_{j}$ $(-10^{9} ≤ l_{j} ≤ r_{j} ≤ 10^{9})$ тоонуудыг оруулна.

Ямар ч үед бүх цэгүүдийн координатууд ялгаатай байна.

Гаралт

Хүсэлтийн 2 төрөл бүрт харгалзах хариултыг нэг мөрөнд хэвлэнэ. Хүсэлтүүдийг оруулсан дарааллын дагуу хариултуудыг хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт %lld буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин cin, cout урсгал эсвэл %I64d хэлбэрийг ашиглавал тохиромжтой.

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

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

Оролт
8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677
Гаралт
176
20
406
1046
1638
156
0
Сэтгэгдлүүдийг ачааллаж байна...