#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define mod 2760727302517
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define pll pair<long long, long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int>
#define vll vector<long long>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ret return
#define present(s, x) (s.find(x) != s.end())
#define cpresent(s, x) (find(all(s), x) != s.end())
#define ford(container, it) for (auto it = container.begin(); it != container.end(); it++)
#define fors(container, it, a, b) for (auto it = a; it != b; it++)
#define ff first
#define all(v) v.begin(), v.end()
#define ss second
#define rep(i, n) for (int i = 0; i < n; i++)
#define fu(i, a, n) for (int i = a; i <= n; i++)
#define fd(i, n, a) for (int i = n; i >= a; i--)
#define INF 1000000000000000003
/*---------------------------------------------------------------------------------------------------------*/
//binary exponentiation
long long int bn(ll a, ll b)
{
ll res = 1;
while (b > 0)
{
if (b & 1)
res = (res * a);
a = a * a;
b >>= 1;
}
return res;
}
void print(bool a)
{
if (a)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
void solve()
{
int t;
cin >> t;
while (t--)
{
ll n, q;
cin >> n >> q;
ll a[n];
fu(i, 1, n)
{
cin >> a[i];
}
ll sumA = 0, sumB = 0;
fu(i, 1, n)
{
sumB += a[i] % mod;
sumA += (a[i] * a[i]) % mod;
}
ll ans = (n * sumA - (sumB * sumB)) % mod;
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
ll x, v;
cin >> x >> v;
ans = ans + n * bn(v, 2) - n * bn(a[x], 2) - bn(v - a[x], 2) - 2 * (sumB) * (v - a[x]);
sumB = sumB - a[x] + v;
a[x] = v;
}
else if (type == 2)
{
ll x, v;
cin >> x >> v;
v += a[x];
ans = ans + n * bn(v, 2) - n * bn(a[x], 2) - bn(v - a[x], 2) - 2 * (sumB) * (v - a[x]);
sumB = sumB - a[x] + v;
a[x] += v -a[x];
}
else{
cout << ans << endl
<< endl;
}
}
}
}
signed main()
{
fast
solve();
return 0;
}