Сережад $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-р үйлдэл бүрийн хувьд тохирох хариуг хэвлэнэ үү.