#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
struct node {
  long long dp[2][2];
  node operator+(const node &o) const {
    node r;
    for (long long i = 0; i < (2); ++i) {
      for (long long j = 0; j < (2); ++j) {
        r.dp[i][j] = -inf;
        r.dp[i][j] = max(dp[i][j], o.dp[i][j]);
        for (long long k = 0; k < (2); ++k)
          r.dp[i][j] = max(r.dp[i][j], dp[i][k] + o.dp[k ^ 1][j]);
      }
    }
    return r;
  }
  node() {}
  node(long long x) {
    dp[1][1] = x;
    dp[0][1] = dp[1][0] = -inf;
    dp[0][0] = -x;
  }
};
template <class T>
struct ST {
  vector<T> st;
  long long n;
  T ini;
  ST(long long n, T ini) : st(2 * n, ini), n(n), ini(ini) {}
  void upd(long long pos, T val) {
    for (st[pos += n] = val; pos /= 2;) st[pos] = st[2 * pos] + st[2 * pos + 1];
  }
  T query(long long x, long long y) {
    T ra = ini, rb = ini;
    bool A = 0, B = 0;
    for (x += n, y += n + 1; x < y; x /= 2, y /= 2) {
      if (x & 1) {
        ra = (!A ? st[x] : ra + st[x]);
        x++;
        A = 1;
      }
      if (y & 1) {
        --y;
        rb = (!B ? st[y] : st[y] + rb);
        B = 1;
      }
    }
    if (!A) return rb;
    if (!B) return ra;
    return ra + rb;
  }
};
const long long N = 300100;
long long n;
long long a[N];
void QUERY() {
  long long q;
  cin >> n >> q;
  ST<node> T(n, node(0));
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    T.upd(i - 1, node(a[i]));
  }
  auto print = [&]() -> void {
    long long res = 0;
    node no = T.query(0, n - 1);
    for (long long i = 0; i < (2); ++i) {
      for (long long j = 0; j < (2); ++j) res = max(res, no.dp[i][j]);
    }
    cout << res << '\n';
  };
  print();
  while (q--) {
    long long l, r;
    cin >> l >> r;
    swap(a[l], a[r]);
    T.upd(l - 1, node(a[l]));
    T.upd(r - 1, node(a[r]));
    print();
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t;
  cin >> t;
  while (t--) {
    QUERY();
  }
}
