Պրեֆիքս (Prefix) գումարների հարցում

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n դրական թվերից կազմված զանգված, պետք է մշակեք q հարցում: Յուրաքանչյուր հարցում կարող է պատկանել հետևյալ երկու տեսակներից որևէ մեկին.

1. Ստուգել, արդյոք զանգվածի որևէ նախաբաժնի գումարը հավասար է տրված s արժեքին:

2. Թարմացնել զանգվածի որևէ ինդեքսում գտնվող արժեքը:

Հարկավոր է ծրագիրը գրել այնպես, որ հարցումներին պատասխանի möglichst արդյունավետ կերպով:

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և q (1 ≤ n, q ≤ 100 000), բաժանված բացատով, որոնք ներկայացնում են զանգվածի չափը և հարցումների քանակը, համապատասխանաբար:

Երկրորդ տողում տրված են n դրական ամբողջ թվեր, որոնք հանդիսանում են զանգվածի էլեմենտները. յուրաքանչյուր էլեմենտ դրական է և չի գերազանցում -ը:

Հաջորդ q տողերում տրվում են հարցումները: Հարցման տիպը նշվում է (1 կամ 2) արժեքով, որին հաջորդում են անհրաժեշտ պարամետրերը.

• Հարցման տիպ 1-ի դեպքում՝ մեկ ամբողջ թիվ s:

• Հարցման տիպ 2-ի դեպքում՝ մեկ դիրք p և արժեք x, որը պետք է դրվի զանգվածի p-րդ ինդեքսում:

Ելք

Յուրաքանչյուր տիպ 1 հարցման դեպքում պետք է տպել YES, եթե գոյություն ունի prefix (նախաբաժին) զանգված, որի գումարը հավասար է s-ին, հակառակ դեպքում պետք է տպել NO:

Օրինակներ