#include <bits/stdc++.h>
#define int long long
using namespace std;
#define Re char y_y
#define rint register int
#define tam cerr << 1e3 * clock ( ) / CLOCKS_PER_SEC << 'm' << 's' << ' ' << ( &y_y - &x_x ) / 1024.0 / 1024.0 << 'M' << 'B' << '\n' , 0
char x_x;
const int N = 5e5 + 5 , inf = 1e16;
char buf[ 1 << 23 ] , *p1 = buf , *p2 = buf , obuf[ 1 << 23 ] , *p3 = obuf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf , 1 , 1 << 23 , stdin ) , p1 == p2 ) ? EOF : *p1 ++ )
#define putchar( x ) ( p3 - obuf < 1 << 23 ) ? ( *p3 ++ = x ) : ( fwrite ( obuf , p3 - obuf , 1 , stdout ) , p3 = obuf , * p3 ++ = x )
template < class T >
inline void read ( T & s )
{
  s = 0; 
  bool q = false;
  char c = getchar ();
  while ( ! isdigit ( c ) ) { if (c == '-') q = true; c = getchar (); }
  while (isdigit (c) ) { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar (); }
  if (q) s = -s;
}
template < class T , class ...Args >
inline void read ( T &s , Args &...x ) { read ( s ) , read ( x... ); }
#define pc putchar
stack < char > so;
template <class S>
inline void print ( S x )
{
  if ( x == 0 ) return pc ( '0' ) , pc ( ' ' ) , void ();
  if ( x < 0 ) x = - x , pc ( '-' );
  while ( x ) { so. push ( x % 10 + 48 ) , x /= 10; }
  while ( ! so. empty () ) pc ( so. top () ) , so. pop ();
  putchar ( ' ' );
}
template <class S , class ...Args>
inline void print ( S x , Args ...y ) { print ( x ) , print ( y ... ); }
#undef pc
inline void flush ( ) { fwrite ( obuf , p3 - obuf , 1 , stdout ) , p3 = obuf; }
#define endl putchar ( '\n' )
int n , m;
namespace Seg
{
  void ckm ( int & x , int y ) { ( y > 0 ) && ( x += y ); }
  void bkm ( int & x , int y ) { ( x < y ) && ( x = y ); }
  struct node 
  { 
    int l , r , maxn , sum , maxni , cnt , se;
    int la1 , la2;//A 中最大值加的值，和下传前la1的历史最大值
    int la3 , la4;//A 中非最大值加的值，和下传前la3的历史最大值
    void clear ( ) { la1 = la2 = la3 = la4 = 0; }
    bool zero ( ) { return ! ( ( la1 != 0 ) || ( la2 != 0 ) || ( la3 != 0 ) || ( la4 != 0 ) ); }
  } e[ N << 2 ];
  #define l( p ) e[ p ]. l
  #define r( p ) e[ p ]. r
  #define maxn( p ) e[ p ]. maxn
  #define sum( p ) e[ p ]. sum
  #define maxni( p ) e[ p ]. maxni
  #define cnt( p ) e[ p ]. cnt
  #define se( p ) e[ p ]. se
  #define la1( p ) e[ p ]. la1
  #define la2( p ) e[ p ]. la2
  #define la3( p ) e[ p ]. la3
  #define la4( p ) e[ p ]. la4
  #define clear( p ) e[ p ]. clear ()
  #define mid( p ) ( e[ p ]. l + e[ p ]. r >> 1 )
  #define ls( p ) ( p << 1 )
  #define rs( p ) ( p << 1 | 1 )
  #define len( p ) ( r ( p ) - l ( p ) + 1 )
  #define zero( p ) e[ p ]. zero ( )
  void pushup ( int p ) 
  {
    maxn ( p ) = max ( maxn ( ls ( p ) ) , maxn ( rs ( p ) ) );
    maxni ( p ) = max ( maxni ( ls ( p ) ) , maxni ( rs ( p ) ) );
    sum ( p ) = sum ( ls ( p ) ) + sum ( rs ( p ) );
    if ( ! ( maxn ( ls ( p ) ) ^ maxn ( rs ( p ) ) ) )
    {
      se ( p ) = max ( se ( ls ( p ) ) , se ( rs ( p ) ) );
      cnt ( p ) = cnt ( ls ( p ) ) + cnt ( rs ( p ) );   
      return;
    }
    else if ( maxn ( ls ( p ) ) > maxn ( rs ( p ) ) )
    {
      se ( p ) = max ( se ( ls ( p ) ) , maxn ( rs ( p ) ) );
      cnt ( p ) = cnt ( ls ( p ) );
    }
    else
    {
      se ( p ) = max ( se ( rs ( p ) ) , maxn ( ls ( p ) ) );
      cnt ( p ) = cnt ( rs ( p ) );
    }
  }
  void updata ( int p , int val1 , int val2 , int val3 , int val4 ) // 最大值 ， 历史最大值 ， 非最大值 ， 历史非最大值
  {
    sum ( p ) += val1 * cnt ( p ) + ( len ( p ) - cnt ( p ) ) * val3;
    bkm ( maxni ( p ) , maxn ( p ) + val2 );
    maxn ( p ) += val1;
    if ( se ( p ) != - inf ) se ( p ) += val3;
    bkm ( la2 ( p ) , la1 ( p ) + val2 ); la1 ( p ) += val1;
    bkm ( la4 ( p ) , la3 ( p ) + val4 ); la3 ( p ) += val3;  
  }
  void pushdown ( int p )
  {
    if ( zero ( p ) ) return;
    int z = max ( maxn ( ls ( p ) ) , maxn ( rs ( p ) ) );
    if ( z == maxn ( ls ( p ) ) ) updata ( ls ( p ) , la1 ( p ) , la2 ( p ) , la3 ( p ) , la4 ( p ) );
    else updata ( ls ( p ) , la2 ( p ) , la2 ( p ) , la3 ( p ) , la4 ( p ) );
    if ( z == maxn ( rs ( p ) ) ) updata ( rs ( p ) , la1 ( p ) , la2 ( p ) , la3 ( p ) , la4 ( p ) );
    else updata ( rs ( p ) , la2 ( p ) , la2 ( p ) , la3 ( p ) , la4 ( p ) );
    clear ( p );
  }
  void build ( int p , int l , int r )
  { 
    l ( p ) = l , r ( p ) = r , se ( p ) = -inf;
    clear ( p );
    if ( ! ( l ^ r ) )
    {
      int x; read ( x );
      sum ( p ) = maxn ( p ) = maxni ( p ) = x; cnt ( p ) = 1;
      return;
    }
    build ( ls ( p ) , l , mid ( p ) );
    build ( rs ( p ) , mid ( p ) + 1 , r );
    pushup ( p );
  }
  void modify ( int p , int l , int r , int val ) // 区加
  {
    if ( l <= l ( p ) && r ( p ) <= r )
    {
      updata ( p , val , max ( 0ll , val ) , val , max ( 0ll , val ) );
      return;
    }
    pushdown ( p );
    int mid = mid ( p );
    if ( l <= mid ) modify ( ls ( p ) , l , r , val );
    if ( r > mid ) modify ( rs ( p ) , l , r , val );
    pushup ( p );
  } 
  void change ( int p , int l , int r , int val ) // 区min
  { 
    if ( val >= maxn ( p ) ) return;
    if ( l <= l ( p ) && r ( p ) <= r && se ( p ) < val && val < maxn ( p ) )
    {
      updata ( p , val - maxn ( p ) , val - maxn ( p ) , 0 , 0 );
      return;
    }
    pushdown ( p );
    int mid = mid ( p );
    if ( l <= mid ) change ( ls ( p ) , l , r , val );
    if ( r > mid ) change ( rs ( p ) , l , r , val );
    pushup ( p );
  }   
  int querysum ( int p , int l , int r )
  {
    if ( l <= l ( p ) && r ( p ) <= r ) 
      return sum ( p );
    pushdown ( p );
    int mid = mid ( p ) , res = 0;
    if ( l <= mid ) res += querysum ( ls ( p ) , l , r );
    if ( r > mid ) res += querysum ( rs ( p ) , l , r );
    return res;
  }
  int querymaxn ( int p , int l , int r )
  {
    if ( l <= l ( p ) && r ( p ) <= r ) 
      return maxn ( p );
    pushdown ( p );
    int mid = mid ( p ) , res = 0;
    if ( l <= mid ) bkm ( res , querymaxn ( ls ( p ) , l , r ) );
    if ( r > mid ) bkm ( res , querymaxn ( rs ( p ) , l , r ) );
    return res;
  }
  int querymaxni ( int p , int l , int r )
  {
    if ( l <= l ( p ) && r ( p ) <= r ) 
      return maxni ( p );
    pushdown ( p );
    int mid = mid ( p ) , res = 0;
    if ( l <= mid ) bkm ( res , querymaxni ( ls ( p ) , l , r ) );
    if ( r > mid ) bkm ( res , querymaxni ( rs ( p ) , l , r ) );
    return res;
  }
}
Re; signed main ()
{ 
  read ( n , m );
  Seg :: build ( 1 , 1 , n );
  while ( m -- )
  {
    int opt , l , r , v;
    read ( opt , l , r );
    if ( opt == 1 )
      read ( v ) , Seg :: modify ( 1 , l , r , v );
    else if ( opt == 2 )
      read ( v ) , Seg :: change ( 1 , l , r , v ); 
    else if ( opt == 3 )
      print ( Seg :: querysum ( 1 , l , r ) ) , endl;
    else if ( opt == 4 )
      print ( Seg :: querymaxn ( 1 , l , r ) ) , endl;
    else
      print ( Seg :: querymaxni ( 1 , l , r ) ) , endl;
  }
  return flush ( ) , 0;
}