#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
template <int, typename T>
struct MINMAX {
  T val;
  MINMAX(T val) : val(val) {}
};
template <typename T>
MINMAX<1, T> MAX(T val) {
  return MINMAX<1, T>(val);
};
template <typename T>
MINMAX<2, T> MIN(T val) {
  return MINMAX<2, T>(val);
};
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<1, U> rhs) {
  return lhs = max(lhs, rhs.val);
}
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<2, U> rhs) {
  return lhs = min(lhs, rhs.val);
}
template <typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
inline vector<T> READ(int n) {
  vector<T> vec(n);
  for (int i = 0; i < int(n); i++) cin >> vec[i];
  return vec;
}
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T> >;
struct node {
  signed long long int mp, pm, mm, pp;
  void merge(node lc, node rc) {
    mp = max(lc.mp, rc.mp);
    mp |= MAX(lc.mp + rc.mp);
    mp |= MAX(lc.mm + rc.pp);
    pm = max(lc.pm, rc.pm);
    pm |= MAX(lc.pm + rc.pm);
    pm |= MAX(lc.pp + rc.mm);
    mm = max(lc.mm, rc.mm);
    mm |= MAX(lc.mp + rc.mm);
    mm |= MAX(lc.mm + rc.pm);
    pp = max(lc.pp, rc.pp);
    pp |= MAX(lc.pm + rc.pp);
    pp |= MAX(lc.pp + rc.mp);
  }
};
struct SegTree {
  static const int NINF = -1e9;
  static const int H = 20;
  static const int N = 1 << H;
  node t[2 * N];
  ;

 private:
  void update(int ID) { t[ID].merge(t[(ID << 1)], t[(ID << 1 | 1)]); }

 public:
  void setPoint(int pos, int val, int ID = 1, int L = 0, int R = N - 1) {
    if (L == R) {
      t[ID] = {NINF, NINF, -val, val};
      return;
    }
    int mid = L + R >> 1;
    if (pos <= mid)
      setPoint(pos, val, ID * 2, L, mid);
    else
      setPoint(pos, val, ID * 2 + 1, mid + 1, R);
    update(ID);
  }
};
SegTree st;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << fixed << setprecision(12);
  int T;
  cin >> T;
  while (T--) {
    int n, q;
    cin >> n >> q;
    vector<int> a = READ<int>(n);
    for (int i = 0; i < int(n); i++) st.setPoint(i, a[i]);
    cout << st.t[1].pp << endl;
    for (int qq = 0; qq < int(q); qq++) {
      int l, r;
      cin >> l >> r;
      l--;
      r--;
      swap(a[l], a[r]);
      st.setPoint(l, a[l]);
      st.setPoint(r, a[r]);
      cout << st.t[1].pp << endl;
    }
    for (int i = 0; i < int(n); i++) st.setPoint(i, 0);
  }
}
