B. Сережа болон жагсаалт

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

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

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

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

Сережад $n$ элементтэй $a_1, a_2, ..., a_n$ жагсаалт өгөгдсөн. Сережа нь түүн дээр $m$ үйлдэл хийхээр болсон. Үйлдэл бүрт нь дараах 3-н аль нэг нь байна.

  • Жагсаалтын $v_i$ дахь элементэд $x_i$ утга олгох. Өөрөөр хэлбэл $a_{v_i} = x_i$.
  • Жагсаалтын элемент бүрийг $y_i$-р нэмэгдүүлэх. Өөрөөр хэлбэл $a_i = a_i + y_i (1 ≤ i ≤ n)$
  • Жагсаалтын $q_{i}$-р элементийг хэвлэх. Энэ элемент нь $a_{q_i}$.

Эдгээр үйлдлүүдийг хийхэд Сережад тусла.

Оролт

Эхний мөрөнд $n, m (1 ≤ n, m ≤ 10^5)$ хоёр бүхэл тоо өгөгдөнө. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ элементтэй $a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) $ анхны жагсаалт өгөгдөнө.

Дараагийн $m$ ширхэг мөр бүрт Сережагийн хийх үйлдэлүүд өгөгдөнө. Эхний тоо нь $t(1 ≤ t_i ≤ 3) $ байна. Хэрвээ $t=1$ байх юм бол $v_i$ болон $x_i$, $(1 ≤ v_i ≤ n, 1 ≤ x_i ≤ 10^9)$ хоёр тоо өгөгдөнө. Хэрвээ $t=2$ байх юм бол $y_i (1 ≤ y_i ≤ 104)$ өгөгдөнө. Хэрвээ $t=3$ байх юм бол $q_i (1 ≤ q_i ≤ n)$ өгөгдөнө.

Гаралт

3-р үйлдэл бүрийн хувьд тохирох хариуг хэвлэнэ үү.

Орчуулсан: Хүрэлцоож

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

Оролт
10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9
Гаралт
2
9
11
20
30
40
39
Сэтгэгдлүүдийг ачааллаж байна...