/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-29-10.04
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;

struct Node
{
      int has [ 2 ][ 2 ];
      long long ma [ 2 ][ 2 ];
} tre [ 100000 * 4 ];


Node Union( Node a , Node b )
{
      Node c;
      //首先 四种起始和终止情况可以直接继承于左儿子或右儿子的对应情况，取最大
      for( int i = 0; i <= 1; i ++ )
            for( int j = 0; j <= 1; j ++ )
            {
                  c . has [ i ][ j ] = a . has [ i ][ j ] | b . has [ i ][ j ];
                  if( a . has [ i ][ j ] && b . has [ i ][ j ] )
                        c . ma [ i ][ j ] = max( a . ma [ i ][ j ], b . ma [ i ][ j ] );
                  else if( a . has [ i ][ j ] )
                        c . ma [ i ][ j ] = a . ma [ i ][ j ];
                  else if( b . has [ i ][ j ] )
                        c . ma [ i ][ j ] = b . ma [ i ][ j ];
            }
      for( int i = 0; i <= 1; i ++ )
            for( int j = 0; j <= 1; j ++ )
                  for( int k = 0; k <= 1; k ++ )
                        if( a . has [ i ][ j ] && b . has [ ! j ][ k ] )
                              if( c . has [ i ][ k ] )
                                    c . ma [ i ][ k ] = max( c . ma [ i ][ k ], a . ma [ i ][ j ] + b . ma [ ! j ][ k ] );
                              else
                                    c . has [ i ][ k ] = 1 , c . ma [ i ][ k ] = a . ma [ i ][ j ] + b . ma [ ! j ][ k ];
      return c;
}

void build( int num , int le , int ri )
{
      memset( tre [ num ]. has , 0 , sizeof( tre [ num ]. has ) );
      if( le == ri )
      {
            int a;
            scanf( "%d" , & a );
            tre [ num ]. has [ le % 2 ][ le % 2 ] = 1;
            tre [ num ]. ma [ le % 2 ][ le % 2 ] = a;
            return ;
      }
      int mid = ( le + ri ) / 2;
      build( num * 2 , le , mid );
      build( num * 2 + 1 , mid + 1 , ri );
      tre [ num ] = Union( tre [ num * 2 ], tre [ num * 2 + 1 ] );
}

void update( int num , int le , int ri , int x , int y )
{
      if( le == ri )
      {
            memset( tre [ num ]. has , 0 , sizeof( tre [ num ]. has ) );
            tre [ num ]. has [ le % 2 ][ le % 2 ] = 1;
            tre [ num ]. ma [ le % 2 ][ le % 2 ] = y;
            return ;
      }
      int mid = ( le + ri ) / 2;
      if( x <= mid )
            update( num * 2 , le , mid , x , y );
      else
            update( num * 2 + 1 , mid + 1 , ri , x , y );
      tre [ num ] = Union( tre [ num * 2 ], tre [ num * 2 + 1 ] );
}

Node query( int num , int le , int ri , int x , int y )
{
      if( x <= le && y >= ri )
            return tre [ num ];
      int flag1 = 0 , flag2 = 0;
      Node x1 , x2;
      int mid = ( le + ri ) / 2;
      if( x <= mid )
            x1 = query( num * 2 , le , mid , x , y ), flag1 = 1;
      if( y > mid )
            x2 = query( num * 2 + 1 , mid + 1 , ri , x , y ), flag2 = 1;
      if( flag1 == 0 )
            return x2;
      if( flag2 == 0 )
            return x1;
      return Union( x1 , x2 );
}
int main()
{
      int T;
      cin >> T;
      while( T -- )
      {
            int n , m;
            cin >> n >> m;
            build( 1 , 1 , n );
            for( int i = 1; i <= m; i ++ )
            {
                  int x , y , z;
                  scanf( "%d%d%d" , & x , & y , & z );
                  if( x == 0 )
                  {
                        Node t = query( 1 , 1 , n , y , z );
                        long long ans;
                        int flag = 0;
                        for( int i = 0; i <= 1; i ++ )
                              for( int j = 0; j <= 1; j ++ )
                                    if( t . has [ i ][ j ] )
                                          if( flag == 0 ) ans = t . ma [ i ][ j ], flag = 1;
                                          else ans = max( ans , t . ma [ i ][ j ] );
                        cout << ans << endl;
                  }
                  else update( 1 , 1 , n , y , z );
            }
      }
      return 0;
}