AlgoLiga 2018

Mieszkańcy p państw położonych wzdłuż linii wybrzeża naszego kontynentu mają już dość noszenia ogromnej liczby monet w swoich sakiewkach, które pod ich ciężarem często się przerywają. W związku z powyższym władcy niektórych krajów sąsiadujących ze sobą raz na jakiś czas podejmują próbę wprowadzenia nowej waluty, minimalizując jednocześnie liczbę monet będących w obiegu. Niestety próby te przeważnie kończą się niepowodzeniem. Czasami wynika to ze zmiany liczby monet w jednym z państw, co powoduje konieczność rozpoczęcia obliczeń od nowa. Innym razem władcy zdążą się pokłócić przed wprowadzeniem nowej waluty i formują inną grupę krajów. Jako, że masz już dość zaistniałej sytuacji, postanowiłeś napisać program, który przyspieszy obliczenia.

Program powinien umożliwiać wykonanie dowolnej liczby operacji. Możliwe operacje to:

• Zmiana liczby monet w państwie na pozycji a na wartość b.
• Obliczenie ile łącznie monet należy wybić, w przypadku gdy nową walutę chcą wprowadzić kraje znajdujące się na pozycjach od a do b włącznie. Należy pamiętać, że liczba monet powinna być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musi być identyczny jak w przypadku starej waluty. W związku z tym, że jest to jedynie symulacja liczba monet w danych państwach nie ulega zmianie.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz q (1 ≤ p, q ≤ 10⁵) oznaczające odpowiednio liczbę państw oraz liczbę operacji do wykonania. W drugiej linii wejścia znajduje się p liczb z przedziału od 1 do 10⁹ określających bieżącą liczbę monet w danym państwie. W kolejnych q liniach znajdują się zapytania. Każde z nich składa się z trzech liczb t, a oraz b. Liczba t (0 ≤ t ≤ 1) określa typ operacji do wykonania. Wartość t równa 0 określa, że należy zaktualizować liczbę monet w państwie a (1 ≤ a ≤ p) na liczbę b (1 ≤ b ≤ 10⁹). Wartość t równa 1 określa konieczność obliczenia łącznej liczby monet do wybicia dla państw w przedziale od a do b (1 ≤ a < b ≤ p).

Wyjście

Dla każdego zapytania z t równym 1 należy w osobnej linii wypisać łączną liczbę monet nowej waluty jakie zostaną wybite dla państw w przedziale od a do b.

Przykład

Wejście

4 5
2 8 4 6
1 1 4
1 2 3
0 1 8
0 4 8
1 1 4

Wyjście

10
3
7