მხოლოდ ფენვიკი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია N ცალი მთელი რიცხვი. უნდა შევასრულოთ Q ცალი ოპერაცია. ოპერაციები სულ 2 ტიპისაა:

* 1 X Y - X ინდექსზე ჩაწერილი რიცხვი შევცვალოთ Y რიცხვით.

* 2 L R - გამოვიტანოთ [L, R] ინდექსებს შორის არსებული რიცხვების ჯამი (L და R ინდექსებზე არსებული ელემენტების ჩათვლით).

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი N (1 <= N <= 10^6) და Q (1 <= Q <= 10^5). მეორე სტრიქონში N ცალი მთელი რიცხვი დიაპაზონში 1..100000.

გამოსატანი მონაცემები: მეორე ტიპის ყველა ოპერაციაზე თითო რიცხვი - ელემენტების ჯამი მითითებული ინტერვალიდან.




მაგალითები

შესატანი მონაცემები
5 5 2 3 4 8 9 1 0 3 2 0 1 2 0 4 1 2 5 2 0 3 დაკოპირება
გამოსატანი მონაცემები
6 27 19 დაკოპირება