#include <bits/stdc++.h>

using namespace std;

struct node_t{
  long long value;
  int lazy;

  /// should be a neutral node for both lazy and query operations
  node_t(){ 
    value = lazy = 0;
  }

  /// aditional constructors for specific problem
  node_t(int value){
    this->value = value;
    this->lazy = 0;
  }
  
  /// associative internal operation 
  node_t operator + (const node_t &other)const{
    return node_t((this->value > other.value ? this->value:other.value));
  }

  /// internal propagation law
  node_t propagate(int lazy,int st,int dr){
    this->lazy += lazy;
    this->value += (dr - st + 1) * value;
  }
};

template <class T>
class SegmentTree{
  int n;
  vector<T> aint;

  void build(int nod,int st,int dr,const vector<T> &v){
    if(st == dr){
      aint[nod] = v[st];
      return ;
    }
    
    int mid = (st + dr) / 2;

    build(nod * 2,st,mid,v);
    build(nod * 2 + 1,mid + 1,dr,v);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  void propagate(int nod,int st,int dr){
    if(aint[nod].lazy == T().lazy || st == dr){
      return ;
    }
    int mid = (st + dr) / 2;
    aint[nod * 2].propagate(aint[nod].lazy,st,mid);
    aint[nod * 2 + 1].propagate(aint[nod].lazy,mid + 1,dr);
    aint[nod].lazy = T().lazy;
  }
  
  ///change lazy here
  void updateAdd(int nod,int st,int dr,int l,int r,int lazy){
    propagate(nod,st,dr);

    if(dr < l || st > r){
      return ;
    }

    if(l <= st && dr <= r){
      aint[nod].propagate(lazy,st,dr);
      return ;
    }
    
    int mid = (st + dr) / 2;

    updateAdd(nod * 2,st,mid,l,r,lazy);
    updateAdd(nod * 2 + 1,mid + 1,dr,l,r,lazy);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  void updateSet(int nod,int st,int dr,int pos,const T &value){
    propagate(nod,st,dr);

    if(dr < pos || st > pos){
      return ;
    }

    if(st == dr){
      aint[nod] = value;
      return ;
    }

    int mid = (st + dr) / 2;

    updateSet(nod * 2,st,mid,pos,value);
    updateSet(nod * 2 + 1,mid + 1,dr,pos,value);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  T query(int nod,int st,int dr,int l,int r){
    propagate(nod,st,dr);

    if(dr < l || st > r){
      return T();
    }

    if(l <= st && dr <= r){
      return aint[nod];
    }


    int mid = (st + dr) / 2;

    return query(nod * 2,st,mid,l,r) + query(nod * 2 + 1,mid + 1,dr,l,r);
  }

  public:
  
  SegmentTree(const vector<T> &v){
    this->n = v.size();
    this->aint = vector<T>(4 * n + 5,T());

    build(1,0,n - 1,v);
  }

  ///update with a node
  void updateSet(int pos,T val){
    updateSet(1,0,n - 1,pos,val);
  }
  
  ///update with a lazy
  void updateAdd(int pos,int val){
    updateAdd(1,0,n - 1,pos,pos,val);
  }

  void updateAdd(int l,int r,int val){
    updateAdd(1,0,n - 1,l,r,val);
  }

  T query(int l,int r){
    return query(1,0,n - 1,l,r);
  }
};

int main(){

  freopen("arbint.in","r",stdin);
  freopen("arbint.out","w",stdout);

  int n,m;
  scanf("%d %d",&n,&m);
  vector<node_t> values(n,node_t());

  for(auto &it:values){
    int value;
    scanf("%d",&value);
    it = node_t(value);
  }

  SegmentTree<node_t> aint(values);

  while(m--){
    int t,l,r;
    scanf("%d %d %d",&t,&l,&r);

    if(t == 1){
      aint.updateSet(l - 1,node_t(r));
    }else{
      printf("%lld\n",aint.query(l - 1,r - 1).value);
    }
  }

  return 0;
}