#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            for (int i = l; i <= r; ++i) a[i] += k;
        } else {
            int l, r;
            cin >> l >> r;
            // Tính số giai đoạn
            // Công thức: sum(a[i]) - sum(min(a[i], a[i-1]))
            // Hoặc đơn giản là greedily build theo thứ tự từ trái sang phải
            // Giai đoạn = a[l] + sum(max(0, a[i] - a[i-1])) for i in l+1..r
            long long ans = a[l];
            for (int i = l + 1; i <= r; ++i) {
                if (a[i] > a[i-1]) ans += (a[i] - a[i-1]);
            }
            cout << ans << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

int n, m;
ll a[MAXN];

// Cây phân đoạn để lưu:
// 1. Giá trị a[i] (phục vụ tính min(a[i], a[i-1]))
// 2. Giá trị diff[i] = max(0, a[i] - a[i-1])
// 3. Tổng diff
// 4. Phép cập nhật range add

struct Node {
    ll sum_diff;
    ll val_first; // a[l] của node này
    ll val_last;  // a[r] của node này
    ll lazy;
} tree[4 * MAXN];

void push_down(int id, int l, int r) {
    if (tree[id].lazy != 0) {
        int mid = (l + r) / 2;
        // Update left child
        tree[id*2].lazy += tree[id].lazy;
        tree[id*2].val_first += tree[id].lazy;
        tree[id*2].val_last += tree[id].lazy;
        // Update right child
        tree[id*2+1].lazy += tree[id].lazy;
        tree[id*2+1].val_first += tree[id].lazy;
        tree[id*2+1].val_last += tree[id].lazy;

        tree[id].lazy = 0;
    }
}

void update_node(int id, ll val) {
    tree[id].lazy += val;
    tree[id].val_first += val;
    tree[id].val_last += val;
}

void pull_up(int id, int l, int r) {
    int mid = (l + r) / 2;
    tree[id].val_first = tree[id*2].val_first;
    tree[id].val_last = tree[id*2+1].val_last;

    // Tính lại sum_diff
    // sum_diff = sum_diff(left) + sum_diff(right) + correction
    // correction = max(0, val_left_last - val_right_first)
    // Lưu ý: sum_diff của node con chưa bao gồm hiệu giữa các node con.
    // Thực tế, diff[i] phụ thuộc vào a[i] và a[i-1].
    // Nếu ta định nghĩa node涵盖 [L, R], sum_diff là sum_{i=L+1}^{R} max(0, a[i]-a[i-1])
    // Thì khi gộp 2 node [L, M] và [M+1, R]:
    // sum_diff = sum_diff(L, M) + sum_diff(M+1, R) + max(0, a[M+1] - a[M])

    ll correction = max(0LL, tree[id*2+1].val_first - tree[id*2].val_last);
    tree[id].sum_diff = tree[id*2].sum_diff + tree[id*2+1].sum_diff + correction;
}

void build(int id, int l, int r) {
    tree[id].lazy = 0;
    if (l == r) {
        tree[id].sum_diff = 0; // diff[l] không tồn tại (phụ thuộc a[l-1])
        tree[id].val_first = a[l];
        tree[id].val_last = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    pull_up(id, l, r);
}

void update(int id, int l, int r, int u, int v, ll val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        update_node(id, val);
        return;
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    pull_up(id, l, r);
}

ll query_val(int id, int l, int r, int pos) {
    if (l == r) return tree[id].val_first;
    push_down(id, l, r);
    int mid = (l + r) / 2;
    if (pos <= mid) return query_val(id*2, l, mid, pos);
    else return query_val(id*2+1, mid+1, r, pos);
}

ll query_diff(int id, int l, int r, int u, int v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[id].sum_diff;
    push_down(id, l, r);
    int mid = (l + r) / 2;
    ll left = query_diff(id*2, l, mid, u, v);
    ll right = query_diff(id*2+1, mid+1, r, u, v);

    // Nếu[left] và [right]被完全分离，需要加上中间的连接项
    // 仅当两个区间相邻且都有效时
    if (max(u, l) <= mid && mid+1 <= min(v, r)) {
        // Need correction between mid and mid+1
        ll val_mid = tree[id*2].val_last; // a[mid] after push down? No, need actual value.
        // Correct way: Query a[mid] and a[mid+1] explicitly
        ll a_mid = query_val(id*2, l, mid, mid);
        ll a_mid_next = query_val(id*2+1, mid+1, r, mid+1);
        left += max(0LL, a_mid_next - a_mid);
    }
    return left + right;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            update(1, 1, n, l, r, k);
        } else {
            int l, r;
            cin >> l >> r;
            ll val_l = query_val(1, 1, n, l);
            ll diff_sum = 0;
            if (l < r) diff_sum = query_diff(1, 1, n, l + 1, r);
            cout << val_l + diff_sum << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

int n, m;
ll a[MAXN];
ll c[MAXN]; // c[i] = a[i] - a[i-1]

struct Fenwick {
    ll bit[MAXN];
    void update(int i, ll val) {
        for (; i <= n; i += i & -i) bit[i] += val;
    }
    ll query(int i) {
        ll sum = 0;
        for (; i > 0; i -= i & -i) sum += bit[i];
        return sum;
    }
    ll query(int l, int r) {
        return query(r) - query(l - 1);
    }
} f_a, f_c;

void update_diff(int i, ll val) {
    // Diff[i] = max(0, c[i])
    // We need to maintain sum of max(0, c[i]).
    // Since c[i] changes, we need to update the sum.
    // However, max(0, c[i]) is not linear.
    // We need a structure that supports range add on c, and range query on max(0, c).
    // But notice: Range add on a implies c[L] += k, c[R+1] -= k.
    // c[i] for i in (L, R] remains unchanged.
    // So c changes at L and R+1.
    // At these points, we can update the contribution to sum of max(0, c[i]).
}

// Solution using two Fenwick trees:
// 1. BIT for a (range add, point query) -> to get a[i]
// 2. BIT for c (range add, point query) -> to get c[i]
// Wait, we need sum of max(0, c[i]).
// Let's use the property: Total stages = a[L] + sum_{i=L+1}^R max(0, a[i]-a[i-1])
// a[L] = sum_{k=1}^L c[k]
// sum_{i=L+1}^R max(0, c[i])
// Total = sum_{k=1}^L c[k] + sum_{i=L+1}^R max(0, c[i])
// This formula is not convenient for range updates.

// Let's try another formula: Total = a[R] + sum_{i=L}^{R-1} max(0, a[i]-a[i+1])
// Or simply: Total = a[L] + sum_{i=L+1}^R max(0, a[i]-a[i-1])
// Range update [L, R] + k:
// a[L...R] += k.
// c[L] += k (since a[L] - a[L-1] increases by k)
// c[R+1] -= k (since a[R+1] - a[R] decreases by k)
// c[i] unchanged for L < i <= R.
// So we need to support updating c at L and R+1.
// We also need to query sum of max(0, c[i]) over a range.
// Since c[i] changes by specific values at specific points, we can just update the BIT storing max(0, c[i]) at those points.

// Wait, what about the a[L] term?
// a[L] = sum_{j=1}^L c[j].
// If we use a Fenwick tree for c, we can get a[L].

// So the plan:
// Maintain Fenwick tree for c.
// Maintain Fenwick tree for D, where D[i] = max(0, c[i]).
// When we update c[L] += k:
//   old_c = c[L], new_c = c[L] + k
//   old_D = max(0, old_c), new_D = max(0, new_c)
//   update D[L] by (new_D - old_D)
//   update c[L] in c-BIT by k
// Similarly for c[R+1] -= k.

// But wait, there is a catch.
// The formula is Total = a[L] + sum_{i=L+1}^R D[i].
// a[L] = sum_{j=1}^L c[j].
// sum_{i=L+1}^R D[i] = sum_{i=L+1}^R max(0, c[i]).

// So we need two BITs:
// BIT_C: stores c[i]. Supports range sum query (to get a[L]).
// BIT_D: stores D[i] = max(0, c[i]). Supports range sum query.

// However, we need to handle updates to c.
// We can't just "add k" to a range in BIT_D because max(0, x) is not linear.
// But notice: Range update on a only changes c at L and R+1.
// So we only need to update BIT_D at L and R+1.

// Algorithm:
// 1. Initialize arrays a and c.
//    c[i] = a[i] - a[i-1] (for i > 1), c[1] = a[1].
//    Build BIT_C from c.
//    Build BIT_D from D[i] = max(0, c[i]).
// 2. Process event type 1 (L, R, k):
//    Update c[L] += k. Update BIT_C. Update BIT_D.
//    If R+1 <= n: Update c[R+1] -= k. Update BIT_C. Update BIT_D.
// 3. Process event type 2 (L, R):
//    ans = query(BIT_C, 1, L) + query(BIT_D, L+1, R)
//    print ans.

void solve() {
    cin >> n >> m;
    // Reset BITs
    memset(f_a.bit, 0, sizeof(f_a.bit));
    memset(f_c.bit, 0, sizeof(f_c.bit));

    vector<ll> c(n + 1);
    vector<ll> a(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // Initialize c and BITs
    // We need to build BIT_D which stores max(0, c[i]).
    // Since we update point by point, we can just loop and add.

    c[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        c[i] = a[i] - a[i-1];
    }

    // We need a separate array for D values to track changes, or just recalc on update.
    // Let's use a global array `current_c` and `current_D`.

    for (int i = 1; i <= n; ++i) {
        f_c.update(i, c[i]);
        f_a.update(i, max(0LL, c[i])); // Using f_a for D values (misnamed in struct but ok)
    }
    // Wait, f_a is used for D in my thought process.
    // Let's rename struct to BIT.

    // Actually, let's just use the code logic.
    // We need to store current c[i] to know the old value of max(0, c[i]).

    // Resetting for the code below:
    // struct BIT { ... } bit_c, bit_d;
    // current_c[i] array.
    // current_d[i] array.
}

struct BIT {
    ll tree[100005];
    void add(int i, ll v) { for (; i <= n; i += i & -i) tree[i] += v; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }
    ll query(int l, int r) { return sum(r) - sum(l-1); }
};

void run() {
    cin >> n >> m;
    vector<ll> a(n + 2), c(n + 2);
    BIT bit_c, bit_d;

    // Clean trees
    for(int i=0; i<=n+1; ++i) { bit_c.tree[i] = 0; bit_d.tree[i] = 0; }

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    c[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        c[i] = a[i] - a[i-1];
    }

    for (int i = 1; i <= n; ++i) {
        bit_c.add(i, c[i]);
        bit_d.add(i, max(0LL, c[i]));
    }

    while (m--) {
        int type; cin >> type;
        if (type == 1) {
            int l, r, k; cin >> l >> r >> k;

            // Update c[l]
            ll old_c = c[l];
            c[l] += k;
            bit_c.add(l, k);

            ll old_D = max(0LL, old_c);
            ll new_D = max(0LL, c[l]);
            bit_d.add(l, new_D - old_D);

            // Update c[r+1]
            if (r + 1 <= n) {
                old_c = c[r+1];
                c[r+1] -= k;
                bit_c.add(r+1, -k);

                old_D = max(0LL, old_c);
                new_D = max(0LL, c[r+1]);
                bit_d.add(r+1, new_D - old_D);
            }
        } else {
            int l, r; cin >> l >> r;
            // a[L] = sum(c[1]...c[L])
            // sum_{i=L+1}^R max(0, c[i])
            ll ans = bit_c.sum(l);
            if (l < r) ans += bit_d.query(l + 1, r);
            cout << ans << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) run();
    return 0;
}