// Author:  HolyK
// Created: Sun Aug  8 18:17:17 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline int mod(LL x) {
  return x % P;
}
inline int reduce(int x) {
  return x >= P ? x - P : x;
}
inline int norm(int x) {
  return x < 0 ? x + P : x;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
using Info = std::array<int, 2>;
Info &operator+=(Info &a, Info b) {
  inc(a[0], b[0]);
  inc(a[1], b[1]);
  return a;
}
Info &operator-=(Info &a, Info b) {
  inc(a[0], P - b[0]);
  inc(a[1], P - b[1]);
  return a;
}
Info operator+(Info a, Info b) {
  return a += b;
}
Info operator-(Info a, Info b) {
  return a -= b;
}
Info operator*(Info a, Info b) {
  return {mod(1LL * a[0] * b[0]), mod(1LL * a[0] * b[1] + 1LL * a[1] * b[0])};
}
Info operator*(Info a, LL b) {
  return {mod(a[0] * b), mod(a[1] * b)};
}
using Poly = std::array<Info, 21>;
constexpr int N(1 << 20);
int n, len, cnt[N];
void fwt(Poly *a) {
  for (int i = 1; i < len; i <<= 1) {
    for (int j = 0; j < len; j += i * 2) {
      for (int k = 0; k < i; k++) {
        for (int p = 0; p <= n; p++) {
          a[i + j + k][p] += a[j + k][p];
        }
      }
    }
  }
}
void ifwt(Poly *a) {
  for (int i = 1; i < len; i <<= 1) {
    for (int j = 0; j < len; j += i * 2) {
      for (int k = 0; k < i; k++) {
        for (int p = 0; p <= n; p++) {
          a[i + j + k][p] -= a[j + k][p];
        }
      }
    }
  }
}
const auto Inv = [] {
  std::array<int, 21> c;
  c[0] = c[1] = 1;
  for (int i = 2; i < 21; i++) {
    c[i] = 1LL * (P - P / i) * c[P % i] % P;
  }
  return c;
}();
Poly ln(Poly a) {
  Poly b;
  for (int i = 0; i < n; i++) b[i] = a[i + 1] * (i + 1);
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
      b[i] = b[i] - a[j] * b[i - j];
    }
  }
  for (int i = n; i; i--) {
    b[i] = b[i - 1] * Inv[i];
  }
  b[0].fill(0);
  return b;
}
Poly f[N];
Info a[N];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  len = 1 << n;
  for (int i = 1; i < len; i++) {
    cnt[i] = 1 + cnt[i & i - 1];
  }
  for (int i = 0; i < len; i++) {
    a[i] = {1, 0};
  }
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      int x;
      std::cin >> x;
      a[1 << i | 1 << j] = {x + 1, x};
    }
  }
  for (int i = 1; i < len; i <<= 1) {
    for (int j = 0; j < len; j += i * 2) {
      for (int k = 0; k < i; k++) {
        a[i + j + k] = a[j + k] * a[i + j + k];
      }
    }
  }
  for (int i = 0; i < len; i++) f[i][cnt[i]] = a[i];
  fwt(f);
  for (int i = 0; i < len; i++) {
    f[i] = ln(f[i]);
  }
  // ifwt(f);
  // std::cout << f[len - 1][n][1] << "\n";
  int ans = 0;
  for (int i = 0; i < len; i++) {
    if (cnt[i] & 1) {
      inc(ans, P - f[i][n][1]);
    } else {
      inc(ans, f[i][n][1]);
    }
  }
  if (n & 1) ans = P - ans;
  std::cout << ans % P << "\n";
  return 0;
}

// Author:  HolyK
// Created: Sat Aug  7 20:25:17 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(2e5 + 5);
int n, c[N], a[N];
void add(int p) {
  for (; p <= n; p += p & -p) c[p] ^= 1;
}
void add(int l, int r) {
  add(l), add(r + 1);
}
int ask(int p) {
  int r = 0;
  for (; p; p -= p & -p) r ^= c[p];
  return r;
}

#define ls o << 1
#define rs o << 1 | 1
int pos[N << 2], cnt[N << 2];

int ask(int o, int l, int r, int x) {
  if (a[x] > a[pos[o]]) return 0;
  int ans = 0;
  while (l < r) {
    int m = l + r >> 1;
    if (a[pos[ls]] >= a[x]) {
      ans += cnt[o] - cnt[ls];
      o = ls;
      r = m;
    } else {
      o = rs;
      l = m + 1;
    }
  }
  assert(a[l] >= a[x]);
  return ans += ask(x) ^ ask(l);
}
void build(int o, int l, int r) {
  if (l == r) {
    pos[o] = l;
    cnt[o] = 0;
    return;
  }
  int m = l + r >> 1;
  build(ls, l, m), build(rs, m + 1, r);
  pos[o] = a[pos[ls]] > a[pos[rs]] ? pos[ls] : pos[rs];
  cnt[o] = cnt[ls] + ask(rs, m + 1, r, pos[ls]);
}
void update(int o, int l, int r, int x) {
  if (l == r) return;
  int m = l + r >> 1;
  x <= m ? update(ls, l, m, x) : update(rs, m + 1, r, x);
  pos[o] = a[pos[ls]] > a[pos[rs]] ? pos[ls] : pos[rs];
  cnt[o] = cnt[ls] + ask(rs, m + 1, r, pos[ls]);
}

int p, s;
void solve(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    if (!p) {
      p = pos[o];
      s = cnt[o];
    } else if (a[pos[o]] >= a[p]) {
      s += ask(o, l, r, p), p = pos[o];
    }
    return;
  }
  int m = l + r >> 1;
  if (x <= m) solve(ls, l, m, x, y);
  if (y > m) solve(rs, m + 1, r, x, y);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    int x;
    std::cin >> x;
    if (x) add(i, i);
  }
  build(1, 1, n);
  int q;
  std::cin >> q;
  while (q--) {
    int opt, x, y;
    std::cin >> opt >> x >> y;
    if (opt == 1) {
      a[x] = y;
      update(1, 1, n, x);
    } else if (opt == 2) {
      add(x, y);
      update(1, 1, n, x);
      update(1, 1, n, y);
    } else {
      p = s = 0;
      solve(1, 1, n, x, y);
      std::cout << s << "\n";
    }
      
  }
  return 0;
}

// Author:  HolyK
// Created: Sun Aug  8 09:01:25 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(2e5 + 5), T(768);
int n, a[N], b[N], c[N], d[N], f[N], t[N];
std::vector<int> s[N / T + 5];
void build(int x) {
  auto &q = s[x];
  q.clear();
  int l = x * T, r = std::min(n, l + T);
  for (int i = r - 1; i >= l; i--) {
    while (!q.empty() && a[q.back()] < a[i]) q.pop_back();
    if (q.empty()) {
      f[i] = t[i] = i;
      d[i] = 0;
    } else {
      f[i] = q.back();
      t[i] = t[f[i]];
      d[i] = d[f[i]] + (b[i] ^ b[f[i]]);
    }
    q.push_back(i);
  }
  std::reverse(q.begin(), q.end());
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    std::cin >> b[i];
  }
  int tot = (n - 1) / T + 1;
  for (int i = 0; i < tot; i++) {
    build(i);
  }
  int q;
  std::cin >> q;
  while (q--) {
    int opt, x, y;
    std::cin >> opt >> x >> y;
    if (opt == 1) {
      a[--x] = y;
      build(x / T);
    } else if (opt == 2) {
      x--, y--;
      int bx = x / T, by = y / T;
      if (bx == by) {
        for (int i = x; i <= y; i++) b[i] ^= 1;
        build(bx);
      } else {
        for (int i = x; i < bx * T + T; i++) b[i] ^= 1;
        for (int i = by * T; i <= y; i++) b[i] ^= 1;
        build(bx), build(by);
        for (int i = bx + 1; i < by; i++) c[i] ^= 1;
      }
    } else {
      x--, y--;
      int ans = 0;
      while (x <= y) {
        if (x == t[x]) {
          int to = y + 1;
          for (int i = x / T + 1; i < tot; i++) {
            if (a[s[i].back()] < a[x]) continue;
            to = *std::lower_bound(s[i].begin(), s[i].end(), x, [&](int i, int j) {
              return a[i] < a[j];
            });
            if (to <= y) {
              ans += b[x] ^ b[to] ^ c[x / T] ^ c[i];
            }
            break;
          }
          x = to;
        } else if (t[x] <= y) {
          ans += d[x];
          x = t[x];
        } else if (f[x] <= y) {
          ans += b[x] ^ b[f[x]];
          x = f[x];
        } else {
          break;
        }
      }
      std::cout << ans << "\n";
    }
  }
  return 0;
}

// Author:  HolyK
// Created: Sat Aug 14 10:09:34 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) {
  return x % P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z(int v = 0) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z inv() const {
    assert(x);
    return Z(fpow(x));
  }
  Z pow(int k) const {
    return Z(fpow(x, k));
  }
  Z &operator+=(const Z &r) {
    inc(x, r.x);
    return *this;
  }
  Z &operator-=(const Z &r) {
    dec(x, r.x);
    return *this;
  }
  Z &operator*=(const Z &r) {
    x = 1LL * x * r.x % P;
    return *this;
  }
  Z &operator/=(const Z &r) {
    x = 1LL * x * fpow(r.x) % P;
    return *this;
  }
  Z operator+(const Z &r) const {
    return Z(*this) += r;
  }
  Z operator-(const Z &r) const {
    return Z(*this) -= r;
  }
  Z operator*(const Z &r) const {
    return Z(*this) *= r;
  }
  Z operator/(const Z &r) const {
    return Z(*this) /= r;
  }
  Z operator-() const {
    return Z(P - x);
  }
  operator int() const {
    return x;
  }
};
// det(xI + A)
std::vector<Z> charPoly(std::vector<std::vector<Z>> a) {
  int n = a.size();
  for (int j = 0; j < n - 2; j++) {
    for (int i = j + 1; i < n; i++) {
      if (!a[i][j]) continue;
      std::swap(a[i], a[j + 1]);
      for (int k = 0; k < n; k++) {
        std::swap(a[k][i], a[k][j + 1]);
      }
      break;
    }
    if (a[j + 1][j]) {
      auto inv = a[j + 1][j].inv();
      for (int i = j + 2; i < n; i++) {
        auto c = a[i][j] * inv;
        for (int k = 0; k < n; k++) a[i][k] -= a[j + 1][k] * c;
        for (int k = 0; k < n; k++) a[k][j + 1] += a[k][i] * c;
      }
    }
  }
  std::vector<std::vector<Z>> h(n + 1);
  h[0] = {1};
  for (int i = 0; i < n; i++) {
    Z prod = 1;
    h[i + 1].resize(h[i].size() + 1);
    for (int j = 0; j < h[i].size(); j++) {
      h[i + 1][j + 1] = h[i][j];
      h[i + 1][j] += h[i][j] * a[i][i];
    }
    for (int j = 0; j < i; j++) {
      prod *= -a[i - j][i - j - 1];
      auto c = a[i - j - 1][i] * prod;
      for (int k = 0; k < h[i - j - 1].size(); k++) {
        h[i + 1][k] += h[i - j - 1][k] * c;
      }
    }
  }
  return h[n];
}

int main() {
  // freopen("24.in", "r", stdin);
  // freopen("t.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, d;
  std::cin >> n >> d;
  d++;
  std::vector m(d, std::vector(n, std::vector<Z>(n)));
  for (int i = 0; i < d; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        std::cin >> m[i][j][k].x;
      }
    }
  }
  
  auto row = [&](int x, int y, Z z) {
    for (int i = 0; i < d; i++) {
      for (int j = 0; j < n; j++) {
        m[i][y][j] += m[i][x][j] * z;
      }
    }
  };
  auto col = [&](int x, int y, Z z) {
    for (int i = 0; i < d; i++) {
      for (int j = 0; j < n; j++) {
        m[i][j][y] += m[i][j][x] * z;
      }
    }
  };
  int cnt = 0;
  Z prod = 1;
  auto &h = m[d - 1];
  for (int i = 0, j; i < n; i++) {
    while (!h[i][i]) {
      for (j = i; j < n; j++) {
        if (!h[j][i]) continue;
        if (i != j) {
          prod *= -1;
          for (int k = 0; k < d; k++) {
            std::swap(m[k][i], m[k][j]);
          }
        }
        break;
      }
      if (j < n) break;
      if (++cnt > n * (d - 1)) {
        for (int i = 0; i <= n * (d - 1); i++) {
          std::cout << "0" << " \n"[i == n * (d - 1)];
        }
        return 0;
      }
      for (j = i - 1; j >= 0; j--) {
        if (!h[j][i]) continue;
        col(j, i, -h[j][i] / h[j][j]);
      }
      for (int k = d - 1; k > 0; k--) {
        for (j = 0; j < n; j++) {
          m[k][j][i] = m[k - 1][j][i];
        }
      }
      for (int j = 0; j < n; j++) {
        m[0][j][i] = 0;
      }
    }
    prod *= h[i][i];
    Z inv = h[i][i].inv();
    for (int k = 0; k < d; k++) {
      for (j = 0; j < n; j++) {
        m[k][i][j] *= inv;
      }
    }
    for (j = 0; j < n; j++) {
      if (j == i || !h[j][i]) continue;
      row(i, j, -h[j][i]);
    }
  }
  auto out = [&](auto a) {
    for (int i = 0; i < a.size(); i++) {
      for (int j = 0; j < a[i].size(); j++) {
        std::cerr << a[i][j] << " \n"[j + 1 == a[i].size()];
      }
    }
  };
  
  // out(h);
  // out(m[0]);
  d--;
  std::vector a(n * d, std::vector<Z>(n * d));
  for (int i = 0; i < d; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        a[n * (d - 1) + j][n * i + k] = m[i][j][k];
      }
    }
  }
  for (int i = n; i < n * d; i++) {
    a[i - n][i] = -1;
  }
  // out(a);
  auto f = charPoly(a);
  for (auto &x : f) x *= prod;
  std::vector<int> g(n * d + 1);
  for (int i = cnt; i < f.size(); i++) g[i - cnt] = f[i];
  for (int i = 0; i <= n * d; i++) {
    std::cout << g[i] << " \n"[i == n * d];
  }
  return 0;
}

// Author:  HolyK
// Created: Sat Aug  7 12:43:24 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(6e5 + 5);
int n, m, in[N], out[N], cnt;
std::vector<int> g[N], h[N];
std::vector<std::pair<int*, int>> rec;
int max[N << 2], tag[N << 2];
void record(int &x) {
  rec.emplace_back(&x, x);
}
#define ls o << 1
#define rs o << 1 | 1
// void pushup(int o) {
//   record(max[o]);
//   max[o] = std::max({max[ls], max[rs], tag[o]});
// }
void update(int o, int l, int r, int x, int y, int z) {
  record(max[o]);
  max[o] = z;
  if (x <= l && r <= y) {
    record(tag[o]);
    tag[o] = z;
    return;
  }
  int m = l + r >> 1;
  if (x < m) update(ls, l, m, x, y, z);
  if (y > m) update(rs, m, r, x, y, z);
}
int ask(int o, int l, int r, int x, int y) {
  if (r <= x || y <= l) return 0;
  if (x <= l && r <= y) {
    return max[o];
  }
  int m = l + r >> 1;
  return std::max({ask(ls, l, m, x, y), ask(rs, m, r, x, y), tag[o]});
}
void dfs2(int x, int p) {
  in[x] = cnt++;
  for (int y : h[x]) {
    if (y == p) continue;
    dfs2(y, x);
  }
  out[x] = cnt;
}
int s[N], top, m2, ans;
int t[1 << 21];
void up(int x) {
  for (int i = m2 + x >> 1; i; i >>= 1) {
    t[i] = std::max(t[i << 1], t[i << 1 | 1]);
  }
}
void dfs1(int x, int p) {
  s[++top] = x;
  t[top + m2] = ask(1, 0, n, in[x], out[x]), up(top);
  int l = 0, r = m2 * 2, rmax = 0;
  for (int o = 1; r - l > 1; ) {
    int m = l + r >> 1;
    if (std::max(rmax, t[o << 1 | 1]) >= m) {
      o = o << 1 | 1;
      l = m;
    } else {
      smax(rmax, t[o << 1 | 1]);
      o = o << 1;
      r = m;
    }
  }
  if (rmax >= l) l++;
  // std::cerr << x << " " << top - l + 1 << "\n";
  smax(ans, top - l + 1);
  int now = rec.size();
  update(1, 0, n, in[x], out[x], top);
  for (int y : g[x]) {
    if (y == p) continue;
    dfs1(y, x);
  }
  t[top + m2] = 0, up(top);
  top--;
  while (rec.size() > now) {
    *rec.back().first = rec.back().second;
    rec.pop_back();
  }
}
void solve() {
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    g[i].clear();
    h[i].clear();
  }
  cnt = ans = 0;
  for (int i = 1, x, y; i < n; i++) {
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 1, x, y; i < n; i++) {
    std::cin >> x >> y;
    h[x].push_back(y);
    h[y].push_back(x);
  }
  m = 1 << std::__lg(n * 2 - 1);
  m2 = 1 << std::__lg(n * 2 + 1);
  dfs2(1, 0);
  // std::cerr << "dfs2 end\n";
  dfs1(1, 0);
  std::cout << ans << "\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

// Author:  HolyK
// Created: Sat Aug  7 12:06:08 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

int c[1000006];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    std::cin >> x;
    c[x]++;
  }
  n = 1e6;
  LL ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; i * j <= n; j++) {
      int k = i * j;
      
      ans += 1LL * c[i] * c[j] * c[k];
      
    }
  }
  std::cout << ans << "\n";
  return 0;
}

// Author:  HolyK
// Created: Sat Aug  7 14:36:07 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(2e5 + 5), K((1 << 30) - 1);
int n, q, a[N], b[N];
void brute() {
  while (q--) {
    int l, r, k;
    std::cin >> l >> r >> k;
    std::vector<int> c {a[l]};
    for (int i = l + 1; i <= r; i++) {
      c.push_back((b[i] + k) % k);
    }
    std::sort(c.begin(), c.end());
    std::vector<LL> pre(r - l + 1);
    for (int i = 0; i < r - l + 1; i++) {
      pre[i] = c[i];
    }
    for (int i = 1; i < r - l + 1; i++) {
      pre[i] += pre[i - 1];
    }
    LL ans = std::min(pre.back(), 1LL * (r - l + 1) * k - pre.back());
    // std::cerr << pre.back() << " ";
    for (int x = 0; x < r - l + 1; x++) {
      // std::cerr << std::max(pre[x], 1LL * (r - l - x) * k - pre.back() + pre[x]) << " \n"[x == r - l];
      smin(ans, std::max(pre[x], 1LL * (r - l - x) * k - pre.back() + pre[x]));
    }
    std::cout << ans << "\n";
    // return;
  }
}
struct Node {
  int ls, rs, cnt;
  LL sum;
} t[N * 60];
int cur;
void ins(int &o, int l, int r, int x, int y) {
  t[++cur] = t[o], o = cur;
  t[o].cnt++;
  t[o].sum += y;
  if (r - l == 1) return;
  int m = l + r >> 1;
  x < m ? ins(t[o].ls, l, m, x, y) : ins(t[o].rs, m, r, x, y);
}
int cnt;
LL sum;
void ask(int p, int q, int l, int r, int x, int y) {
  // std::cerr << " ?? " << l << " " << r << " " << x << " " << y << "\n";
  if (r <= x || y <= l || t[p].cnt - t[q].cnt == 0) return;
  if (x <= l && r <= y) {
    cnt += t[p].cnt - t[q].cnt;
    sum += t[p].sum - t[q].sum;
    return;
  }
  int m = l + r >> 1;
  if (x < m) ask(t[p].ls, t[q].ls, l, m, x, y);
  if (y > m) ask(t[p].rs, t[q].rs, m, r, x, y);
}
int root[N][2];
LL negSum[N];
int negCnt[N];
std::vector<int> c[2];
signed main() {
  // freopen("k.in", "r", stdin);
  // freopen("k.out", "w", stdout);
  double sta = (double)clock() / CLOCKS_PER_SEC;
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> q;
  for (int i = 1; i <= n; i++) std::cin >> a[i], b[i] = a[i];
  for (int i = n; i; i--) b[i] -= b[i - 1];

  for (int i = 2; i <= n; i++) {
    negSum[i] = negSum[i - 1];
    negCnt[i] = negCnt[i - 1];
    if (b[i] < 0) {
      negSum[i] += b[i], negCnt[i]++; 
    }
    c[b[i] >= 0].push_back(b[i]);
  }
  for (auto &v : c) {
    std::sort(v.begin(), v.end());
    v.resize(std::unique(v.begin(), v.end()) - v.begin());
  }
  auto lb = [&](int i, int x) {
    int l = 0, r = c[i].size();
    while (l < r) {
      int m = l + r >> 1;
      if (c[i][m] < x) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    return l;
  };
  for (int i = 2; i <= n; i++) {
    root[i][0] = root[i - 1][0];
    root[i][1] = root[i - 1][1];
    int k = b[i] >= 0;
    ins(root[i][k], 0, c[k].size(), lb(k, b[i]), b[i]);
  }
  int pos0 = lb(1, 0), posk;
  while (q--) {
    int l, r, k;
    std::cin >> l >> r >> k;
    posk = lb(0, -k);
    LL s = a[r] + 1LL * (negCnt[r] - negCnt[l]) * k;
    int n = r - l + 1;
    auto cal = [&](int x) {
      int pre = n - x;
      int low = 0, high = k;
      while (low < high) {
        int mid = low + high >> 1;
        cnt = 0;
        ask(root[r][0], root[l][0], 0, c[0].size(), posk, lb(0, mid - k + 1));
        ask(root[r][1], root[l][1], 0, c[1].size(), pos0, lb(1, mid + 1));
        if (a[l] <= mid) cnt++;
        if (cnt < pre) {
          low = mid + 1;
        } else {
          high = mid;
        }
      }
      // std::cerr << "??\n";
      cnt = 0;
      sum = 0;
      ask(root[r][0], root[l][0], 0, c[0].size(), posk, lb(0, low - k));
      sum += 1LL * cnt * k;
      ask(root[r][1], root[l][1], 0, c[1].size(), pos0, lb(1, low));
      if (a[l] < low) cnt++, sum += a[l];
      assert(cnt <= n - x);
      sum += 1LL * (n - x - cnt) * low;
      // std::cerr << n - x << " " << low << " " << cnt << "\n";
      return sum + std::max(0LL, 1LL * x * k - s);
    };
    LL pos = (s + k - 1) / k;
    smin(pos, r - l + 1);
    // std::cerr << "pos : " << pos << "\n";
    LL ans = cal(pos);
    
    if (pos) smin(ans, cal(pos - 1));
    std::cout << ans << "\n";
  }
  std::cerr << "time : " << (double)clock() / CLOCKS_PER_SEC - sta << "\n";
  return 0;
}