暂无测试数据。

题目简介

盖诺赛克特要组建起一支军团！他们的老大——红色盖诺赛克特正在清点人数，首先他需要了解手下们的战斗力，他让盖虫们排成一排，然后对你进行询问，每一次询问的格式都是询问：任两个盖诺赛克特之间所有的盖诺赛克特的战斗力是多少（ 不包括询问中包含的盖虫 ）？并且在询问的同时，红色盖诺赛克特也会更改人员配置，将一个盖虫换成另一个盖虫。

题目数据

输入分为若干行，第一行包含两个整数 \(N,M\) 代表初始盖虫数量与操作及询问的数量。
接下来的一行，有 \(N\) 个整数，分别代表每只盖虫战斗力。
接下来若干行，每行三个整数 \(k,a,b\) ，若 \(k=0\) ，则代表询问，否则代表操作。
操作：将第 \(a\) 只盖虫换成战斗力为 \(b\) 的盖虫。
询问：你需要输出第 \(a\) 只盖虫到第 \(b\) 只盖虫之间所有盖虫的战斗力和（换行）。

样例

输入

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出

11
30
35

数据范围

\(N,M <= 10^5\)