#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,q,l,k; cin>>n>>q,l=(k=__lg(n))>>1;
  vector s(n,vector<int>(k+1));
  for(int i=0;i<n;i++)
    cin>>s[i][0];
  auto bf=[&](){
    for(int i=1;i<=l;i++)
      for(int j=0;j+(1<<i)<=n;j++)
        s[j][i]=abs(s[j][i-1]-s[j+(1<<i-1)][i-1]);
  };
  bf();
  while(q--){
    int op,x,y; cin>>op>>x>>y;
    if(x--;op==1)s[x][0]=y,bf();
    else if(y<=l)cout<<s[x][y]<<'\n';
    else{
      for(int i=l+1;i<=y;i++)
        for(int j=x;j+(1<<i)<=x+(1<<y);j++)
          s[j][i]=abs(s[j][i-1]-s[j+(1<<i-1)][i-1]);
      cout<<s[x][y]<<'\n';
    }
  }
  return 0;
}