#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll noo = numeric_limits<ll>::min() / 2;
struct segtree {
  struct node {
    ll data[4];
    node() {
      get(0, 0) = get(0, 1) = 0;
      get(1, 0) = get(1, 1) = noo;
    }
    node(ll x) {
      get(0, 0) = get(0, 1) = 0;
      get(1, 0) = x;
      get(1, 1) = -x;
    }
    ll& get(ll p, ll d) { return data[(p & 1) * 2 + (d & 1)]; }
    ll get(ll p, ll d) const { return data[(p & 1) * 2 + (d & 1)]; }
    node operator+(const node& o) const {
      node ret;
      for (ll i = 0; i < 2; i++) {
        for (ll j = 0; j < 2; j++) {
          ret.get(i + j, 0) = max(ret.get(i + j, 0),
                                  get(i, 0) + (i ? o.get(j, 1) : o.get(j, 0)));
          ret.get(i + j, 1) = max(ret.get(i + j, 1),
                                  get(i, 1) + (i ? o.get(j, 0) : o.get(j, 1)));
        }
      }
      return ret;
    }
  };
  ll n;
  vector<node> data;
  segtree(ll N) : n(1) {
    while (n < N) n <<= 1;
    data.resize(2 * n);
  }
  void update(ll k, ll x) {
    k += n;
    data[k] = node(x);
    k >>= 1;
    for (; k > 0; k >>= 1) data[k] = data[2 * k] + data[2 * k + 1];
  }
};
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  ll t;
  cin >> t;
  while (t--) {
    ll n, q;
    cin >> n >> q;
    segtree st(n);
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
      cin >> a[i];
      st.update(i, a[i]);
    }
    auto best = st.data[1];
    cout << max(best.get(0, 0), best.get(1, 0)) << "\n";
    while (q--) {
      ll l, r;
      cin >> l >> r;
      l--;
      r--;
      st.update(l, a[r]);
      st.update(r, a[l]);
      swap(a[l], a[r]);
      auto best = st.data[1];
      cout << max(best.get(0, 0), best.get(1, 0)) << "\n";
    }
  }
  return 0;
}
