Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 p x: a_p \gets a_p + x

1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

1 \leq N, Q \leq 500,000

0 \leq a_i, x \leq 10^9

0 \leq p < N

0 \leq l_i < r_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Sample Output 1

15
7
25
6



Sample input:
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3


Sample output:
15
7
25
6

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91Kn?%^00000KmY&$00000a4rA<0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj50000000000000000000000000000006BGad000006BGad00000001BW000000RR911^@s6C>;O*00000C><aG00000C><aG00000@B#n;00000SOow800000001BW000000ssI21^@s6Kpg-800000Kph|e00000Kph|e000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4v=IOR00000v=IOR00000v=IOR00000Q~&?~00000Q~&?~000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4C>;O*00000C><aG00000C><aG00000*a83m00000*a83m000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$r>j4pH^N`vf~XhPTMd8_pm3@$0ssI26#xJL0RR911^@s6000mI0RRL56#xJL000006qpP{bCw4J000000000000000000000000000000ng9R*5&!@I00000000000000000000fdBvi5&!@I00000000000000000000x&QzG5&!@I00000000000000000000$N>NVA^-pY00000000000000000000RR9105&!@I00000000000000000000y8!?I5&!@I00000000000000000000vj6}95&!@I00000000000000000000TLAz75&!@I00000000000000000000ssR815&!@I000000000000000000004FLcE5&!@I00000000000000000000@c;k-5&!@I00000000000000000000VF3UD5&!@I00000000000000000000*8u<k5&!@I00000000000000000000+yDRo5&!@I000000000000000000009{>OVAOHXW00000000000000000000kpTbz5&!@I00000000000000000000-vIys5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000X#fBK5&!@I00000000000000000000c>w?b5dawgKp-Fh000005CH%H00000U;qFB5dawgU?Cs?000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q)zN@MN(-1Us_XiGh=CP0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`Bn0AE^8Q*Sw6O<!qlb7gXLNq9v?Qd4hKUjScPQ*<#mUte@+a&LEEVqs)oVQg$~V|D;vT4Zccb^u>mPE&L^X>W61VqtS-F*S2}Zew3}X>@2`b97{BZ$)ANUtec<cwca3a&vEPVQgu1d0%!g0AE^8Q)w|UUrk?Scyw}MV{}P)MMY9mX;M^Q0AE^DbTKwxUvG1Ca%Ev{UukZ0WpZ>$V^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kP)k!YUu*zhT5fl30AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2m0AE^DbTngcb#wr1X<}z%V_$PFb8jv&0AE#ZcWG{9Us7drb!}w;Y-wU+E^}`#HUM8=b97;2YhPn%YhPwzX>0&rUt@S-Utx4*cxiM1UteQ*VP9rxZeeU`dSw7@Wo>P5c4YuxUu<b&V_$Q0VRCd|ZDDC{07pYZUo$Q+07pzoLPK9NE;Il~Oi4mRUotK-E;Rr{SXe<qNnbH8GXO_SNkT(dSYI<PG%h&+M@&gVLs(c}GcGg$000620{{X51ONg61ONg60ssX70{{a60ssU61^@s62LJ>B000000ssO40ssI2000000RRC2g8={l5C8xGAOHXWP$qc`000L7@c{q;000000RRF3paB2?5C8xGFaQ7m6lrM<000F5`2hd`5C8xGbsA|2000C40|Ed5000000RRI40RR915C8xG00000)30j<000I64*~!H5C8xGiGL{q000938Ug?S5C8xGbSaVu00062C;|Wg00000C><aG000002mk;800000Ko0-_00000FdZNO000002mk;8000005DowU00000I2|AW000002mk;80000001p5F000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s61ONa40000000000*dHJO000001^@s64*&oF0000000000;2$6W000001^@s65dZ)H0000000000=pP^e000001^@s65&!@I0000000000@E;%m000001^@s66951J0000000000_#Yqu000001^@s66aWAK00000000005Fj7`000000RR914gdfE0000000000Kp-Fh000001poj56#xJL0000000000U?Cs?000001poj5761SM0000000000XdfT|000002LJ#70RR910000000000a33H5000002LJ#70ssI20000000000cpo4D000002LJ#70{{R30000000000fFB?L000002LJ#71poj50000000000h#w#T000002LJ#71^@s60000000000kRKob000002LJ#72LJ#70000000000m>(bj000002LJ#72mk;80000000000pdTOr000002LJ#72><{90000000000s2?Bz000002LJ#73IG5A0000000000upb}*000002LJ#73jhEB0000000000xE~+@000002LJ#73;+NC0000000000z#kw0000002LJ#74FCWD0000000000$R8j8000002LJ#75C8xG0000000000NQ3MMNQ(uH6(9geg}`(I|IkQ-#0bLx0000000000|25(iAOQa*<P;zP4<A4P|0UuSAOL6p0002#;Q#;s|0UWKAOL6q0002#(EtDc|0U8CAOL6r0002#!2kdM|0T*4AOL6s0002#u>b%6|0Ti{AOL6t0002#p#T5>|0TK<AOL6u0002#kpKVx|0S{%AOL6v0002#fdBvh|0SvvAOL6w0002#aR2}R|0SXnAOL6x0002#VE_OB|0S9fAOL6y0002#Q2+n`|0R+XAOL6z0002#K>z>$|0RkPAOL6!0002#F#rGm|0RMHAOL6#0002#ApigW|0Q}9AOL2N0000000000L03UmG5<kTK~z;!NP+B#0001FNQ(p|C;$KeNQp!wcrn1}82|tONR4zP3`mVV%oQL2NXG@K79aos0002!4FCWCNR4zP5J-u~=>Puz|43t8Bn(K$L?j>p0000;$3!G300000NXJAZFaQ7m07!+~baqI%|NsC0|Ns9VNIAm~hads~07#82-2eap07!}N=;!|b|40GFNQp!wATiQNiEJb=4<Cd800000NXG=w00000NQ1%wNIBDW??^etNQrDDD0CrAjU_G>AOJ{-!w(+-NQvG|iRb9e{{R0-gTn|&Io);aOpSabKuC>rBp^(Q|L7tE004_bBoK{I|AoMbR3s1&gpmLM07#8&Bos)E9pe-r08EW!Bp6JMY$O~^jdUan4<A4PNQv%9iQniI{{R1rL?jeUiRMU&--W;rg_{5X0O<bx|Nl&h?nsHp==1&m|BFN<7>jfyKuBYJBpidl0Xgt}B1nr&Bw%JP4<Cd800000NMq1Q0X)%(!uQ%C!U51Z@O<ryL?jT6Q2&L%iBu#Ib&gDl|L8^n002mfd?X-9h5vK~=(qj<|1rQwi(DjlWJog{B`5#@01t((0000;fy9Ua003KEL0myyL0&;$!w(;T00000=wto=|4fPQNQuYjSpEP1i$o+Gi&P{SInaJ}NQ-<VU@`U&A4C8ENMp!I12oT#NdF<oIl_GKIl@Sbd?a9g7Y`qR00000NMp)KD>ToIO8+6sIl_PNNR2(25+DHR<oy5tx&Z(H08EMYNQuYBL?jCe=s*4c|BFN<5RFj(g}{kaBoGgUy#D|H=_&vJ|1tLKqv#I(|Nl&h|450$=wkr@07#2`Bp^tI|8xcD)cpVdNQvL*JpKRwNQuMi<mhtz|Nmx?NR2&W6d(XdgX{?C0R8{}NQ*tu5g-6ajTPDvAOJ{>HAEC307!$x2<d|S|Nmx?G3`l-(OyW2;z)z!@K97tjRi^r002mh4buVu07#8J{QUp_{}px-AOQ3aA4C8ENR2(A5g-6nNR0)V5g-6aIrvD4<#ZWHiv>y%AOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2&V5g-6ajWt>kAOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(s#5g-6ag}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIV>&AOHY$FGzzuzYrh*098nd<#Y^4i#_TPAOPqs{Qv*xNdN!;#sx_eAOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8EQ%H&XNQ-|UNQM7&1?X=3|Nlsfdk9E{|8xyo>0kT*{|_I400000Tf=4#A4C8EK~+IiG09a^Ns0AHiTg-{><CPYW(Z6xCP<5J2uLd~NXJJA00000NXJJI00000NXJJQ00000Oo`w~!TkeB!T1A%#Q{i#z=<z(AV|9Z|NsC0|NkFIInWP>K>+{&Oo`{{`1=3<iz`Tp!ASwkNQp}bNQp}jOo?L{NsC1YNsDy=Nr}WsDfCD=@N^DHiO)=l;^-Fp|Nlsd!At?+M2%$uNXJ7U00000NQp}jNXJ7c00000O=ILp$3rjx0000@h2(WuM2$`VG5<v|z(G0rem-U{4<Cd800000NQ*-VgU10m?@Eg_0DT-ti%TGh_zxcdNMq1Q0W{Hx!uQ%C!U51Z=zQ%-gTM$uIr)FgNQ1-(TU|k1L0!X;NVxz1|NsC0{~t*?#CLZ}jV$E=0000;iSOtk`v3n(jSMI;(hna1NXG=w00000NQ1%wNjcPY??{V#AV`TzC`gGzAV`TzFi3^}bOq?$`TzfmE9p-E|Nlsfdmu=O#Ylz!bOq?e`Tze&i+c!2h5vK~=(qX*|451N=pXw3|L9uz|NrP!`Tze9A4C8EL03UmNr~4%RY6otjV0y_AOKZJjV<mAAOKTAiTz25_Dm_|NQ3MMNWuLB=<oRd|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF30UHB5Pyhe`2><{9y!ikBoB#j-ocaI%!~g&Qtoi@{Tmb+8T>St4umJ!7jQs!qYybcNoc;g*+yDRo%>DoW9033TeE<Ld%mDxZ?EnA&6aoMM6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|S82tbLD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|S82JDH-~a#s01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)(D?uV2mk;800000000008~^|STmS$7xcvYBDgXcg06`8Ag92L$4hT#OK@JE28~^|S000000eVnOQUC#X5C@x04Ils;8w>{skO2SyJOBUyBme*asQmx`s{sH21pfd4074EBjRHar7>ol$4j_gEK@KQ`1xgMu0|o&K4k$qmAVCfoLJkl@4hTXEPyhe`WB>pFNcjK%t^xo61lRxo074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-dA4!{8e!vP8oI6)3DK@KQF4j@7f7(xyZLJkN>3jhEB7ytkOFaZDnr27B=E&u=k080)KUJeKV00000L;wH)OaTA@sQv%{WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGlmP$$(Eb1a0ssI20000000000|Nj9MV+8;Jx&j6I0sx!?3IG760|oj50RR6179(~50Nw#0qy+%B0;>Xo1puD~4*&oF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Ko0-_000005DowU0000001p5F000000RR91000000RR91000000RR9100000g8={l000000RR9100000paB2?000003;+NC00000PznG5000004FCWD00000q!9oB0000082|tP00000C><aG000008vp<R000005C8xG000008UO$Q00000I2|AW000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000=mY=&000001^@s600000zybgO000003IG5A00000Gy(ts000003jhEB000007ytkO000006#xJL0000000000000000{{R300000P#+)w000000ssI200000H~|0v000006aWAK000002LJ#7000007XSbN000007zqFX000002LJ#700000;0FKz000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000PzL}200000|NsAQ000000{{R300000@c;jB0000090vdZ00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Kph|e0000000000000000000000000h6(@x00000mI?p>00000rV0Q600000wh90M00000#tHxc00000)(QXs00000<_Z7+00000_6h(1000001`7ZH0000077G9X00000CJO)n00000HVXg%00000MhgG{0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9=mY=&000000000000000000000{{mA90vdZ000000000000000000000{{pBPzL}2000000000000000000000{{sC;0FKz000000000000000000000{{vD7zqFX000000000000000000000{{yEPznG5000000000000000000000{{#Fa0&nb000000000000000000000{{&GPzwM6000000000000000000000{{*HU<&{M000000000000000000000{{;Iq!9oB000000000000000000000{{>Jun_<N000000000000000000000{{^Kv=IOR000000000000000000000{{{L2oeAQ000000000000000000000{{~M;1d7<000000000000000000000{|2NC><aG000000000000000000000{|5OI2|AW000000000000000000000{|8PKph|e000000000000000000000{|BQP#+)w000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90ssyG5DowU00000E&u=k000009RL6T0RR~Qc_JVH000000RR9100000EC2ui1OV~>00000000000000000000Hvj+t0ssyGa1H<f000000000000000IRF3v0ssyGunqtK000000000000000OaK4?0ssyG01p5F000000000000000VgLXD0RR~Qcp@MG000000RR9100000aR2}S0RR;MI2|AW000000000000000m;e9(0ssyGKo0-_000000000000000qyPW_0RR*LC><aG000000000000000EC2ui1OV~>00000000000000000000!vFvP0RR#J+!Fu*000000000000000000001OV~>00000000000000000000(EtDd000pHv=IOR000000000000000<NyEw0RR>NKph|e000000000000000?EnA(000yKI2|AW000000000000000{r~^~000yKC><aG0000000000000005di=I0RR^OP#+)w000000000000000CjkHeA^;8mP!9kA00000DgXcg00000KLG#$5C9ke7$6`3000000000000000dIJCeAOIKu03aX$000000000000000Mgaf-5daVXun_<N000001ONa400000RRI715&!@I00000000000000000000djS9d5&!@I00000000000000000000qX7T_5&!@I00000000000000000000(g6SfA^-pY000000000000000000007ytkO5&#YWU<&{M00000t^xo600000?g0P*A^;8mP!9kA00000DgXcg000001_A&85ds(h2p}K;00000000000000069NDL5&!@I00000000000000000000D*^xjAp#fx5Fj7`000002mk;800000Wdr~K5&#bXq!9oB000000000000000M*;u<A^;8mfDZrw00000s{sH200000aRLAU5&!@I00000000000000000000ivj=u5&!@I00000000000000000000eggmi5&#YWKn?%^00000D*ylh00000p8@~?5&!@I00000000000000000000vH}1AA^;8mfDZrw00000s{sH200000+yVdq5&!@I00000000000000000000>jMA)5&#PTPznG5000000000000000_yPa`5ds(h7$6`30000000000000001Oos75&!@I00000000000000000000VFLgF5dawgKp-Fh000005CH%H00000cmn_c5C9ke03aX$000000000000000`2YX_5C9nffFd9O000000000000000g#!Qp5&!@I00000000000000000000umb=95C9nf7$6`3000000000000000yaNCL5&!@I00000000000000000000;R65w5&#YWFcAO%00000WdHyG00000@dE$=5&!@I000000000000000000001_S^A5&!@I00000000000000000000Cj<ZhAOHXW00000000000000000000Lj(W-5&!@I00000000000000000000TLb_A5&#YWpb-E7000000ssI200000YXkrQ5dawgU?Cs?000007y$qP00000fdl{m5&!@I00000000000000000000pacK_AOHXW00000000000000000000uLJ-9AOHXW00000000000000000000$pioZ5&!@I000000000000000000000BvDuZZ2bE0AEK;PeMUVUte=|VqZyLZDDC{0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44T23)BMrCeyX=7_ta%E*nctu1qMRovRWn^J=VE|uAPhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT251MIbTg*X>N06a&$>}MMY9mZ&Y7EKu1hTLPJ<sUo$Q=E;#^ST251RIB9QlUt(c%Wid5#d2VB0cWHEJUvqS1X>UbhKtM-KNkT(dSYI<PGyq>;V|Za-W@&C=Y-xIBKtM-KNkT(kGA=SMH2_~)PBAe?Wo~zAV{24$Wo1ctMMN=0b^u>rWOHv{Xkl(-Y-IpnT251Ga&tveX+S_nOi4mRSXf^(E;Il{S1xj8W-eb}XLxvDaAk6HZ*F01X>@sCb}#^6T23)BMrCeyX=7_ta%E*nctt}pMN&&sbT)QnV{~tFNqAFXNq9v?0AF8Ycwt{*bY*yHbU;8yOi4mRUotK-E;RsOT4Zccc0fQ!Oi4mRSXf^(E;ImNT5fl3KtM-KNkT(dSYI<PGyq>(PBAe?Wo~zAV{24$Wo1ctMME(~QcF{GHg;uWbZ>G=cvE3Xctu43Ute={VPk7wV`yt%W?^Y;KtM-KNkT(kGA=X#Utd&BLtjNsL|<P3Us_XiF*aXcZ*z2VWnpb!X>N06a&$>!Q*<#gV`yP=UvzR|X>@Z*V?{+$Q*<#iVqtS>V_$D`baG{3ZAnyLR4`vfQ#M~vOH(snY(PLqOi4mRSXf^(E;KGV0AE^DbTngcb#y>LM@&gVLs(c}GcGg$UteTlbYWj}bYXII0AE^8Q)w|UUrk?Scyw}MV{}P)MMY9mX;M^QKtM-KNkT(dSYI<PG%h&+UteN#b6<0GVRCc;Us_I6bU0~mb6;X%b7eG1ZfSHwF-3MjKu1hTLPJ<sUo$Q=0AF8hX<}nvV{>(1X>MtB0BvP$ZEtpEKtM-KNkT(kGA=SMH2_~<XLxvDaAk6HZ*F01X>@sCb}&FdLs(crLP=jSE;9gMNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnRc?1_Ze(9lWpj0HWk5hjLqlIPE-(OJUu<b&V_#!)bzf#_ZfO8tT2pj0V`*+cKu1hTLPJ<sUo$Q=0AF8hX<}nvb97;HbYE>@X>LG3M@&gVLtip3GA=a$Utec!Z*E_6bYXIIUta)UNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`BnKtM-KNkT(dSYI<PGyniDb9rraVPXI-b98caVPXI-b7*sPa&%#004`~6bY*gI04{ECbY(6<LP;%jVP^m?Zf|sDE@y6aE@E|QY-BBIWB@K_ZgnnbVRL8zE@XLbb9rq5E@XLbb98b5E@y6aE_P*db7^mG04`^4buM;ga&u{KZeMZ$E^=jTVJ>8OZU8QFWo%(CaBOq{E@^IQbO0`JY;-PXZ*%}IbY*yS04`=}ZfO86a&Kf|bYTE4WoTb!a$#*{Uua}<04`-{UuJS)ZDjy1XJcbuWq4y{aCBdEVPb4$04`~6X>?y<a&lpL04`=}ZfRd(a&lpL04`*CZeeX{V*oB>VRT^tE@E?Y04`&1ZEa<4bN~PV000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO00000C;|Wg000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000=mY=&00000=mY=&00000Gy(ts0000000000000000RR91000000000000000UH||9|NsAQ0ssI20000090vdZ0000090vdZ00000E&u=k000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000PzL}200000PzL}200000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000;0FKz00000;0FKz00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&000007zqFX000007zqFX00000H~|0v000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000PznG500000PznG5000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000a0&nb00000a0&nb00000-~a#s0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000PzwM600000PzwM6000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000U<&{M00000U<&{M00000LIwZ;0000000000000005C8xG000000000000000qW}N^0RR911^@s600000q!9oB00000q!9oB000002><{90000000000000001ONa4000000000000000sQ>@~0RR915&!@I00000un_<N00000un_<N000001ONa40000000000000001ONa4000001ONa400000u>b%70RR910ssI200000v=IOR00000v=IOR00000Q~&?~0000000000000001ONa4000000000000000zW@LL0RR910ssI2000002oeAQ000002oeAQ00000*Z}|l0000000000000002mk;8000000000000000$p8QV0RR910ssI200000;1d7<00000;1d7<00000GXMYp0000000000000000RR91000000000000000+W-In4gdfE0{{R300000C><aG00000C>;O*000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000I2|AW00000I2`~0000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000Kph|e00000Kpg-8000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000P#+)w00000P#*vQ00000umAu60000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000C<p)m000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000a3}x(00000?gRh;0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000UM&Cs000005CH%H0000000000000000RR91000000000000000"

open("./kyomu", 'wb').write(base64.b85decode(exe_bin))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
A = list(map(int,input().split()))
qs = [tuple(map(int,input().split())) for i in range(Q)]

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bit = BinaryIndexedTree(N)

for i,a in enumerate(A):
    bit.add(i,a)
for q in qs:
    if q[0]:
        l,r = q[1:]
        print(bit.sum(l,r))
    else:
        p,x = q[1:]
        bit.add(p,x)

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    # a[i] = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

def main():
    from sys import stdin
    input = stdin.buffer.readline

    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    bit = BinaryIndexedTree(n)
    for i, ai in enumerate(a):
        bit.add(i, ai)

    ans = []
    for _ in range(q):
        typ, i, j = map(int, input().split())
        if typ == 0:
            bit.add(i, j)
        else:
            ans.append(bit.cumulative_sum(j) - bit.cumulative_sum(i))

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    # a[i] = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

def main():
    from sys import stdin
    input = stdin.buffer.readline

    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    bit = BinaryIndexedTree(n)
    for i, ai in enumerate(a):
        bit.add(i, ai)

    ans = []
    for _ in range(q):
        typ, i, j = map(int, input().split())
        if typ == 0:
            bit.add(i, j)
        else:
            ans.append(bit.cumulative_sum(j) - bit.cumulative_sum(i))

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = LIST()
bit = BIT(N)
for i in range(N):
    bit.add(i, A[i])

for i in range(Q):
    q, a, b = MAP()

    if q == 0:
        bit.add(a, b)
    else:
        ans = bit.query(a, b)
        print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def Add(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n, q = map(int, input().split())
fw = BIT(n+2)
a = list(map(int, input().split()))
for i, x in enumerate(a):
	fw.Add(i+1, x)
for _ in range(q):
	x, y, z = map(int, input().split())
	if x == 0:
		fw.Add(y+1, z)
	else:
		print(fw.Sum(z) - fw.Sum(y))

Submission status: Accepted

Solution code:
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

BIT=[]
N,Q=map(int,input().split())
Binit(BIT,N+1)
A=list(map(int,input().split()))
for i in range(N):
  Badd(BIT,i+1,A[i])
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,input().split())
  if a:
    print(Bssum(BIT,b+1,c))
  else:
    Badd(BIT,b+1,c)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], i8[:]), cache=True)
def main(X, TAB):
    bit = build(X)
    for i in range(0, len(TAB), 3):
        t, a, b = TAB[i:i + 3]
        if t == 0:
            add(bit, a + 1, b)
        else:
            x = get_sum(bit, b) - get_sum(bit, a)
            print(x)

N, Q = map(int, readline().split())
X = np.array([0] + readline().split(), np.int64)
TAB = np.array(read().split(), np.int64)

main(X, TAB)

Submission status: Accepted

Solution code:
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] += self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] = self.data[i + (i & -i)] + self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.data[index] + delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BIT():

    __slots__ = ["func", "e", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())), lambda a, b: a + b, 0)
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.prefix_folded(c) - seg.prefix_folded(b))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 1)
    
    def getsum(self, i):
        ret = 0
        i += 1
        while(i > 0):
            ret += self.BIT[i]
            i -= i & -i
        return ret
    
    def add(self, i, x):
        i += 1
        while(i <= self.n):
            self.BIT[i] += x
            i += i & -i

N, Q = map(int, input().split())
A = list(map(int, input().split()))
bit = Fenwick(N)
for i in range(N):
    bit.add(i, A[i])

for q in range(Q):
    t, a, b = map(int, input().split())
    if t == 0:
        bit.add(a, b)
    else:
        print(bit.getsum(b - 1) - bit.getsum(a - 1))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

a = list(map(int,input().split()))
for i in range(N):
    BIT_update(i+1,a[i])

for i in range(Q):
    a,b,c = map(int,input().split())
    if a == 0:
        BIT_update(b+1,c)
    else:
        print(BIT_query(c)-BIT_query(b))