// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 100005
#define inf 0x3f3f3f3f

int n,q,a[maxn];
int f[maxn][11];

int F(int p,int k){
	if((1<<k)<=512) return f[p][k];
	return abs(F(p,k-1)-F(p+(1<<(k-1)),k-1));
}

void upd(int x,int k){
	if(k==0) f[x][0]=a[x];
	else f[x][k]=abs(f[x][k-1]-f[x+(1<<(k-1))][k-1]);
	if((1<<k)==512) return ;
	if(x+(1<<(k+1))-1<=n) upd(x,k+1);
	if(x-(1<<k)>=1) upd(x-(1<<k),k+1);
}

signed main()
{
	n=read(),q=read();
	For(i,1,n)a[i]=read(),f[i][0]=a[i];
	For(i,1,9)
		For(j,1,n-(1<<i)+1)
			f[j][i]=abs(f[j][i-1]-f[j+(1<<(i-1))][i-1]);
	For(_,1,q){
		int o=read(),x=read(),y=read();
		if(o==1){
			a[x]=y;
			upd(x,0);
		}else{
			cout<<F(x,y)<<"\n";
		}
	}
	return 0;
}
/*
6 7
2 6
4 5
1 2
3 6
3 5
1 4
5 6

6 7
2 5
2 3
3 6
2 4
1 4
1 6
1 5
*/