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

#define int int64_t
#define endl '\n'
#define inf 1e15
#define vi vector<int>
#define pi pair<int, int>
#define F0(n, i) for(int i = 0; i < n; i++)
#define each(a) for(auto& e: a)
#define F first
#define S second

struct node {
	pi mx_pfx, mn_pfx, mx_sfx, mn_sfx, mxs, tot;
	node(int x) {
		mx_pfx = mn_pfx = mx_sfx = mn_sfx = mxs = tot = {x, 1};
	}
	node() {
		mx_pfx = mx_sfx = mxs = {-inf, 0};
		mn_pfx = mn_sfx = {inf, 0};
		tot = {0, 0}; // useless
	}
	void dbg() {
		cerr << mx_pfx.F << ' ' << mn_pfx.F << ' ' << mx_sfx.F << ' ' << mn_sfx.F << ' ' << mxs.F << ' ' << tot.F << endl;
	}
};

template<typename T>
class segtree {
public:
	vector<T> t;
	int n;
	T def;
	function<T(T, T)> fx;
	void build(int _n, T _def, function<T(T, T)> _fx) {
		n = _n; def = _def; fx = _fx;
		t.assign(n * 2, def);
		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
	}
	void build(vector<int>& a, T _def, function<T(T, T)> _fx) {
		n = a.size(); def = _def; fx = _fx;
		t.assign(n * 2, def);
		F0(n, i) t[i + n] = T(a[i]);
		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
	}
	void update(int i, int v) {
		for(t[i += n] = T(v); i > 1; ) {
			i /= 2;
			t[i] = fx(t[i * 2], t[i * 2 + 1]);
		}
	}
	// this query is made on [l, r)
	T query(int l, int r) {
		cerr << l << ' ' << r << endl;
		T lans = def, rans = def;
		for(l += n, r += n; l < r; l /= 2, r /= 2) {
			if(l % 2) lans = fx(lans, t[l++]);
			if(r % 2) rans = fx(t[--r], rans);
		}
		lans.dbg(); rans.dbg();
		return fx(lans, rans);
	}
	void debug() {
		each(t) e.dbg();
	}
};

void solve() {
	int n;
	cin >> n;
	vi a(n);
	F0(n, i) cin >> a[i];
	segtree<node> MaxSum;
	auto fx = [&](node x, node y) {
		node ans;
		//////////
		int mx_pfx = max(x.mx_pfx.F, x.tot.F + (x.tot.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F));
		ans.mx_pfx.F = mx_pfx;
		if(mx_pfx == x.mx_pfx.F) 
			ans.mx_pfx.S = x.mx_pfx.S;
		if(mx_pfx == x.tot.F + (x.tot.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F)) 
			ans.mx_pfx.S = x.tot.S + (x.tot.S % 2 ? y.mn_pfx.S : y.mx_pfx.S);
		//////////
		int mn_pfx = min(x.mn_pfx.F, x.tot.F + (x.tot.S % 2 ? -y.mx_pfx.F : y.mn_pfx.F));
		ans.mn_pfx.F = mn_pfx;
		if(mn_pfx == x.mn_pfx.F) 
			ans.mn_pfx.S = x.mn_pfx.S;
		if(mn_pfx == x.tot.F + (x.tot.S % 2 ? -y.mx_pfx.F : y.mn_pfx.F)) 
			ans.mn_pfx.S = x.tot.S + (x.tot.S % 2 ? y.mx_pfx.S : y.mn_pfx.S);
		//////////
		int mx_sfx = max(y.mx_sfx.F, x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.tot.F : y.tot.F));
		ans.mx_sfx.F = mx_sfx;
		if(mx_sfx == y.mx_sfx.F) 
			ans.mx_sfx.S = y.mx_sfx.S;
		if(mx_sfx == x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.tot.F : y.tot.F)) 
			ans.mx_sfx.S = x.mx_sfx.S + y.tot.S;
		//////////
		int mn_sfx = min(y.mn_sfx.F, x.mn_sfx.F + (x.mn_sfx.S % 2 ? -y.tot.F : y.tot.F));
		ans.mn_sfx.F = mn_sfx;
		if(mn_sfx == y.mn_sfx.F) 
			ans.mn_sfx.S = y.mn_sfx.S;
		if(mn_sfx == x.mn_sfx.F + (x.mn_sfx.S % 2 ? -y.tot.F : y.tot.F)) 
			ans.mn_sfx.S = x.mn_sfx.S + y.tot.S;
		//////////
		int mxs = max({ x.mxs.F, y.mxs.F, x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F) });
		ans.mxs.F = mxs;
		if(mxs == x.mxs.F)
			ans.mxs.S = x.mxs.S;
		if(mxs == y.mxs.F)
			ans.mxs.S = y.mxs.S;
		if(mxs == x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F))
			ans.mxs.S = x.mx_sfx.S + (x.mx_sfx.S % 2 ? y.mn_pfx.S : y.mx_pfx.S);
		//////////
		ans.tot = {x.tot.F + (x.tot.S % 2 ? -y.tot.F : y.tot.F), x.tot.S + y.tot.S};
		return ans;
	};
	MaxSum.build(a, node(), fx);
	int q, mod = 1e9 + 7;
	cin >> q;
	while(q--) {
		int t;
		cin >> t;
		MaxSum.debug();
		cerr << endl;
		if(t == 1) {
			int i, v;
			cin >> i >> v;
			i--;
			MaxSum.update(i, v);
		} else {
			int l, r;
			cin >> l >> r;
			l--;
			node ans = MaxSum.query(l, r);
			cout << ans.mxs.F % mod << ' ';
		}
	}
}

int32_t main() {
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
		cout << endl;
	}
}