Seryoja və massiv

Serejanın $n$ tam ədəddən ibarət $a_1,a_2,...,a_n$ massiv var. Sereja aktiv bir oğlandır və bu səbəbdən $m$ əməliyyat yerinə yetirməyi planlaşdırır. Bu əməliyyatlar aşağıdakı üç növdən birinə aid ola bilər:

• Massivin $v_i$-ci elementini $x_i$-ə bərabər et. Yəni, $a_{v_i}=x_i$ təyin et.

• Massivin hər bir elementini $y_i$ qədər artır. Yəni, hər $i$ üçün $a_i=a_i+y_i(1\le i\le n)$ təyin et.

• Kağıza massivin $q_i$-ci elementini yaz. Yəni, $a_{q_i}$ elementini yaz.

Serejaya kömək edin və onun bütün əməliyyatlarını yerinə yetirin.

Giriş verilənləri

Birinci sətirdə $n,m(1\le n,m\le 10^5)$ tam ədədləri verilib. İkinci sətirdə $n$ tam ədədləri $a_1,a_2,...,a_n(1\le a_i\le 10^9)$ — başlanğıc massiv verilib.

Sonrakı $m$ sətir əməliyyatları təsvir edir, $i$-ci sətir $i$-ci əməliyyatı təsvir edir. $i$-ci sətirdəki ilk ədəd əməliyyatın növünü göstərən $t_i(1\le t_i\le 3)$ tam ədədidir.

• Əgər $t_i=1$ olarsa, iki tam ədəd $v_i$ və $x_i(1\le v_i\le n,1\le x_i\le 10^9)$ verilir.

• Əgər $t_i=2$ olarsa, bir tam ədəd $y_i(1\le y_i\le 10^4)$ verilir.

• Əgər $t_i=3$ olarsa, bir tam ədəd $q_i(1\le q_i\le n)$ verilir.

Çıxış verilənləri

Üçüncü tip əməliyyatların hər biri üçün $a_{q_i}$ dəyərini çıxışa yazın. Dəyərləri giriş məlumatlarında müvafiq sorğuların ardıcıllığı ilə çıxışa verin.

Nümunələr