花神喜歡步行游歷各國(guó)，順便虐爆各地ACMer?；ㄉ裼幸粭l游覽路線，它是線型的，也就是說(shuō)，所有游歷國(guó)家呈一條線的形狀排列，花神對(duì)每個(gè)國(guó)家都有一個(gè)喜歡程度（當(dāng)然花神并不一定喜歡所有國(guó)家）每一次旅行中，花神會(huì)選擇一條旅游路線，它在那一串國(guó)家中連續(xù)的一段，這次旅行帶來(lái)的開(kāi)心值是這些國(guó)家的喜歡度的總和。當(dāng)然花神對(duì)這些國(guó)家的喜歡程度并不是恒定的，有時(shí)會(huì)突然對(duì)某些國(guó)家產(chǎn)生反感，使他對(duì)這些國(guó)家的喜歡度delta變?yōu)?img src="/oj/upload/image/20191203/20191203143025_88568.png" alt="Travel(J)" width="71" height="32" title="Travel(J)" align="" />，也就是開(kāi)根號(hào)（可能遙花神虐爆了那些國(guó)家的ACMer,從而感到乏味）現(xiàn)在給出花神每次的旅行路線，以及開(kāi)心度的變化，請(qǐng)求出花神每次旅行的開(kāi)心值

對(duì)于100%的數(shù)據(jù)，n<=100000,m<=200000,data[i]非負(fù)且小于10^9.

第一行有一個(gè)整數(shù)N表示有N個(gè)國(guó)家

第二行有N個(gè)空格隔開(kāi)的整數(shù)，表示每個(gè)國(guó)家的初始喜歡度data[i]

第三行是一個(gè)整數(shù)M表示有M條信息要處理

第四行到最后，每行3個(gè)整數(shù)，x, l, r, (l<=r)，當(dāng)x=1時(shí)詢問(wèn)游歷國(guó)家l到r的開(kāi)心值總

和，當(dāng)x=2是修改國(guó)家l到r中每個(gè)國(guó)家的喜歡度

注：建議使用sqrt函數(shù)，且向下取整

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

101
11
11