#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")

// hloya template v26

// ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
// ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
// ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
// ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
// █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
// ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
// ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
// ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
// ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
// ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
// ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░

#include <bits/stdc++.h>
using namespace std;

bool dbg = 0;

clock_t start_time = clock();
#define current_time                                                           \
  fixed << setprecision(6) << (ld)(clock() - start_time) / CLOCKS_PER_SEC

#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))

#define ull unsigned long long
#define ll long long
#define ld long double
#define pii pair<int, int>
#define umap unordered_map<int, int>

#define files1 freopen("input.txt", "r", stdin)
#define files2 freopen("output.txt", "w", stdout)
#define files                                                                  \
  files1;                                                                      \
  files2
#define fast_io                                                                \
  ios_base::sync_with_stdio(0);                                                \
  cin.tie(0)

// #define endl '\n'
#define ln(i, n) " \n"[(i) == (n)-1]

void bad(string mes = "NO") {
  cout << mes;
  exit(0);
}
void bad(int mes) {
  cout << mes;
  exit(0);
}

template <typename T> string bin(T x, int st = 2) {
  string ans = "";
  while (x > 0) {
    ans += char('0' + x % st);
    x /= st;
  }
  reverse(ans.begin(), ans.end());
  return ans.empty() ? "0" : ans;
}

mt19937_64 mt_rand(228 // chrono::system_clock::now().time_since_epoch().count()
);

template <typename T1, typename T2> inline bool upmax(T1 &a, T2 b) {
  return (a < b ? (a = b, true) : false);
}
template <typename T1, typename T2> inline bool upmin(T1 &a, T2 b) {
  return (b < a ? (a = b, true) : false);
}

// inline int popcount(int x){
//     int count = 0;
//     __asm__ volatile("POPCNT %1, %0;":"=r"(count):"r"(x):);
//     return count;
// }

// template <typename T> T input() {
//   T ans = 0, m = 1;
//   char c = ' ';

//   while (!((c >= '0' && c <= '9') || c == '-')) {
//     c = getchar();
//   }

//   if (c == '-')
//     m = -1, c = getchar();
//   while (c >= '0' && c <= '9') {
//     ans = ans * 10 + (c - '0'), c = getchar();
//   }
//   return ans * m;
// }

template <typename T> T gcd(T a, T b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}

// template <typename T> void read(T &a) { a = input<T>(); }
// template <typename T> void read(T &a, T &b) { read(a), read(b); }
// template <typename T> void read(T &a, T &b, T &c) { read(a, b), read(c); }
// template <typename T> void read(T &a, T &b, T &c, T &d) {
//   read(a, b), read(c, d);
// }

const int inf = 1e9 + 20;
const short short_inf = 3e4 + 20;
const long double eps = 1e-12;
const int maxn = (int)1e6 + 100, base = 998244353;
const ll llinf = 2e18 + 5;
const int mod = 1e9 + 7;

const int blockSize = 400;

ll tot_add_block[maxn];
vector<tuple<int, int, ll>> as_in_block[maxn]; // a_i, i, suffix_sum
int pointer_to_as_in_block[maxn]; // just shows position in as_in_block for
                                  // every i
int to_add_now[maxn];

vector<ll> solveSMALLBLOCK(int n, int m, int z, vector<int> a,
                           vector<tuple<int, int, int>> queries) {
  vector<ll> ans;

  for (int i = 0; i <= (n - 1) / blockSize; ++i) {
    as_in_block[i].clear();
    tot_add_block[i] = 0;
  }

  for (int i = 0; i < n; ++i) {
    as_in_block[i / blockSize].push_back(make_tuple(a[i], i, 0));
  }
  for (int i = 0; i <= (n - 1) / blockSize; ++i) {
    sort(as_in_block[i].begin(), as_in_block[i].end());
    for (int j = 0; j < (int)as_in_block[i].size(); ++j) {
      pointer_to_as_in_block[get<1>(as_in_block[i][j])] = j;
    }
  }

  auto update = [&](int t, int p, int d, int block_id, int block_start,
                    int block_end) {
    for (int b = 0; b < block_id; ++b) {
      tot_add_block[b] += d;
    }

    for (int i = block_start; i < block_end; ++i) {
      to_add_now[i] = 0;
    }

    for (int i = block_start; i <= p; ++i) {
      int ptr = pointer_to_as_in_block[i];
      to_add_now[i] = 1;
    }

    int tot_add = 0;
    for (int iter_block = (int)as_in_block[block_id].size() - 1;
         iter_block >= 0; --iter_block) {
      auto &[a_i, idx, suffix_sum] = as_in_block[block_id][iter_block];
      tot_add += to_add_now[idx];
      suffix_sum += 1ll * tot_add * d;
    }
  };

  auto query = [&](int t, int p, int d, int block_id, int block_start,
                   int block_end) {
    ll res = 0;

    for (int b = 0; b < block_id; ++b) {
      auto it = lower_bound(as_in_block[b].begin(), as_in_block[b].end(),
                            make_tuple(d, -1, 0)) -
                as_in_block[b].begin();
      if (it != as_in_block[b].size()) {
        int cnt_good_in_block = as_in_block[b].size() - it;
        res += get<2>(as_in_block[b][it]) +
               1ll * cnt_good_in_block * tot_add_block[b];
      }
    }

    for (int i = block_start; i <= p; ++i) {
      if (a[i] >= d) {
        int ptr = pointer_to_as_in_block[i];
        ll val = get<2>(as_in_block[block_id][ptr]);
        ++ptr;
        if (ptr < (int)as_in_block[block_id].size()) {
          val -= get<2>(as_in_block[block_id][ptr]);
        }
        res += val + tot_add_block[block_id];
      }
    }
    return res;
  };

  for (auto [t, p, d] : queries) {
    int block_id = p / blockSize;
    int block_start = block_id * blockSize;
    int block_end = min(n, (block_id + 1) * blockSize);

    // // TODO REMOVE ON SUBMIT
    // if (clock() - start_time > 10. * CLOCKS_PER_SEC) {
    //   break;
    // }

    if (t == 1) {
      update(t, p, d, block_id, block_start, block_end);
    } else {
      ans.push_back(query(t, p, d, block_id, block_start, block_end));
    }
  }
  return ans;
}

const int blockSize2Min = 2245, blockSize2Max = blockSize2Min + 10;
// const int blockSize2 = 2250;
int blockSize2;

short ptr_by_a_in_block[maxn][maxn / blockSize2Min +
                              5]; // ptr_by_a_in_block[b][d] returns first >= d
                                  // in block b

ll ss_in_block[maxn / blockSize2Min + 5][blockSize2Max + 5];
int items_in_block[maxn / blockSize2Min + 5];
char to_add_now_2[blockSize2Max + 5];
ll simpleadd[maxn];

vector<ll> solveLARGEBLOCK(int n, int m, int z, vector<int> a,
                           vector<tuple<int, int, int>> queries) {
  vector<ll> ans;

  //   cerr << sizeof(ptr_by_a_in_block) / sizeof(short) << endl;

  ll min_comp = llinf;
  for (int bsize = blockSize2Min; bsize <= blockSize2Max; ++bsize) {
    ll cur_comp = 0;
    for (auto [t, p, d] : queries) {
      if (t == 2) {
        cur_comp += p % bsize;
      }
    }
    if (upmin(min_comp, cur_comp)) {
      blockSize2 = bsize;
    }
  }

  for (int i = 0; i <= (n - 1) / blockSize2; ++i) {
    // ss_in_block[i].clear();
    items_in_block[i] = 0;
    tot_add_block[i] = 0;
  }
  memset(ptr_by_a_in_block, -1, sizeof(ptr_by_a_in_block));

  for (int i = 0; i < n; ++i) {
    simpleadd[i] = 0;
    int block_start = i / blockSize2 * blockSize2;
    // ss_in_block[i / blockSize2].push_back(0);
    ss_in_block[i / blockSize2][items_in_block[i / blockSize2]] = 0;
    items_in_block[i / blockSize2]++;
  }
  const int max_a = 1e6;

  vector<pii> as_in_block;
  for (int i = 0; i <= (n - 1) / blockSize2; ++i) {
    ss_in_block[i][items_in_block[i]] =
        0; // After all elements + 1 to skip the if later

    int block_start = i * blockSize2;
    int block_end = min(n, (i + 1) * blockSize2);
    as_in_block.clear();
    for (int j = block_start; j < block_end; ++j) {
      as_in_block.push_back(mp(a[j], j));
    }
    sort(all(as_in_block));
    for (int j = 0; j < (int)as_in_block.size(); ++j) {
      int a_val = as_in_block[j].first;
      pointer_to_as_in_block[as_in_block[j].second] = j;
      if (ptr_by_a_in_block[a_val][i] == -1) {
        ptr_by_a_in_block[a_val][i] = j;
      }
    }
    assert(items_in_block[i] + 10 < SHRT_MAX);
    ptr_by_a_in_block[max_a + 1][i] = items_in_block[i];
  }
  for (int d = max_a; d >= 0; --d) {
    for (int i = 0; i <= (n - 1) / blockSize2; ++i) {
      if (ptr_by_a_in_block[d][i] == -1) {
        ptr_by_a_in_block[d][i] = ptr_by_a_in_block[d + 1][i];
      }
    }
  }

  // cerr << current_time << endl;

  auto update = [&](int t, int p, int d, int block_id, int block_start,
                    int block_end) {
    for (int b = 0; b < block_id; ++b) {
      tot_add_block[b] += d;
    }

    for (int i = 0; i < block_end - block_start; ++i) {
      to_add_now_2[i] = 0;
    }

    for (int i = block_start; i <= p; ++i) {
      int ptr = pointer_to_as_in_block[i];
      to_add_now_2[ptr] = 1;
      simpleadd[i] += d;
    }

    int tot_add = 0;
    for (int iter_block = items_in_block[block_id] - 1; iter_block >= 0;
         --iter_block) {
      tot_add += to_add_now_2[iter_block];
      ss_in_block[block_id][iter_block] += 1ll * tot_add * d;
    }
  };

  ans.reserve(z);
  for (auto [t, p, d] : queries) {
    int block_id = p / blockSize2;
    int block_start = block_id * blockSize2;
    int block_end = min(n, (block_id + 1) * blockSize2);

    if (t == 1) {
      update(t, p, d, block_id, block_start, block_end);
    } else {
      ll res = 0;
      for (int b = 0; b < block_id; ++b) {
        short ptr_by_a = ptr_by_a_in_block[d][b];
        int cnt_good_in_block = items_in_block[b] - ptr_by_a;
        res += ss_in_block[b][ptr_by_a];
        res += 1ll * cnt_good_in_block * tot_add_block[b];
      }
      int cnt_good_in_block = 0;
      for (int i = block_start; i <= p; ++i) {
        if (a[i] >= d) {
          res += simpleadd[i];
          ++cnt_good_in_block;
        }
      }
      res += 1ll * cnt_good_in_block * tot_add_block[block_id];
      ans.push_back(res);
      
    }
  }
  //   cerr << "total_update_time = " << total_update_time << endl;
  //   cerr << "total_query_time = " << total_query_time << endl;
  //   cerr << "total_time_1 = " << total_time_1 << endl;
  //   cerr << "total_time_2 = " << total_time_2 << endl;
  return ans;
}

vector<ll> solveBrute(int n, int m, int z, vector<int> a,
                      vector<tuple<int, int, int>> queries) {
  vector<ll> v(n);
  vector<ll> ans;
  // at least one n,m,z <= 216k

  for (auto [t, p, d] : queries) {
    if (t == 1) {
      // m
      for (int j = 0; j <= p; ++j) {
        v[j] += d;
      }
    } else {
      // z
      ll res = 0;
      for (int j = 0; j <= p; ++j) {
        if (a[j] >= d) {
          res += v[j];
        }
      }
      ans.push_back(res);
    }
  }
  return ans;
}

void gen_test(int n, int m, int z, vector<int> &a,
              vector<tuple<int, int, int>> &queries) {
  a.resize(n);

  for (int i = 0; i < n; ++i) {
    a[i] = rand() % (int)1e6 + 1;
    // a[i] = i + 1;
  }
  random_shuffle(a.begin(), a.end());

  queries.resize(m + z);

  // vector<int> block_ends;

  // const int exp_block2_size = 2250;
  // for (int i = 0; i < n; i += exp_block2_size) {
  //   if (i + exp_block2_size - 1 < n) {
  //     block_ends.push_back(i + exp_block2_size - 1);
  //   }
  // }
  // int x = block_ends.back();
  // block_ends = {x};

  for (int i = 0; i < m; ++i) {
    // int p = block_ends[rand() % block_ends.size()];
    queries[i] = make_tuple(1, rand() % n, rand() % (int)1e6 + 1);
  }
  for (int i = 0; i < z; ++i) {
    // int p = block_ends[rand() % block_ends.size()];
    int p = max(0, n - 1 - i % 2000);
    queries[m + i] = make_tuple(2, p, rand() % (int)1e6 + 1);
  }
  random_shuffle(queries.begin(), queries.end());
}

uint64_t vechash(vector<ll> ans) {
  uint64_t res = 0;
  for (auto x : ans) {
    res = res * 31 + x;
  }
  return res;
}

namespace fastIO_hqz {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
// #define ll long long
// fread->read
bool IOerror = 0;
inline char nc() {
  static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, BUF_SIZE, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
    //{printf("IO error!\n");system("pause");for (;;);exit(0);}
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror)
    return;
  if (ch == '-')
    sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())
    x = x * 10 + ch - '0';
  if (sign)
    x = -x;
}
inline void read(ll &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror)
    return;
  if (ch == '-')
    sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())
    x = x * 10 + ch - '0';
  if (sign)
    x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror)
    return;
  if (ch == '-')
    sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())
    x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign)
    x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror)
    return;
  for (; !blank(ch) && !IOerror; ch = nc())
    *s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc())
    ;
  if (IOerror) {
    c = -1;
    return;
  }
}
// getchar->read
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-')
      bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo)
    x = -x;
}
inline void read1(ll &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-')
      bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo)
    x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-')
      bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9';
         tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar())
      ;
  }
  if (bo)
    x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar())
    *s++ = ch;
  *s = 0;
}
inline void read1(char &c) {
  for (c = getchar(); blank(c); c = getchar())
    ;
}
// scanf->read
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(ll &x) {
#ifdef _WIN32
  scanf("%I64d", &x);
#else
#ifdef __linux
  scanf("%lld", &x);
#else
  puts("error:can't recognize the system!");
#endif
#endif
}
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
// inline void readln2(char *s){gets(s);}
// fwrite->write
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[BUF_SIZE];
    p1 = buf;
    pend = buf + BUF_SIZE;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, BUF_SIZE, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x)
      *s1++ = '0';
    if (x < 0)
      out('-'), x = -x;
    while (x)
      *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)
      out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x)
      *s1++ = '0';
    if (x < 0)
      out('-'), x = -x;
    while (x)
      *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)
      out(*s1);
    out('\n');
  }
  void print(ll x) {
    static char s[25], *s1;
    s1 = s;
    if (!x)
      *s1++ = '0';
    if (x < 0)
      out('-'), x = -x;
    while (x)
      *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)
      out(*s1);
  }
  void println(ll x) {
    static char s[25], *s1;
    s1 = s;
    if (!x)
      *s1++ = '0';
    if (x < 0)
      out('-'), x = -x;
    while (x)
      *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)
      out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static ll mul[] = {1,
                       10,
                       100,
                       1000,
                       10000,
                       100000,
                       1000000,
                       10000000,
                       100000000,
                       1000000000,
                       10000000000LL,
                       100000000000LL,
                       1000000000000LL,
                       10000000000000LL,
                       100000000000000LL,
                       1000000000000000LL,
                       10000000000000000LL,
                       100000000000000000LL};
    if (x < -1e-12)
      out('-'), x = -x;
    x *= mul[y];
    ll x1 = (ll)floor(x);
    if (x - floor(x) >= 0.5)
      ++x1;
    ll x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      for (size_t i = 1; i < y && x3 * mul[i] < mul[y]; out('0'), ++i)
        ;
      print(x3);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) {
    while (*s)
      out(*s++);
  }
  void println(char *s) {
    while (*s)
      out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(ll x) { Ostream.print(x); }
inline void println(ll x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
// puts->write
char Out[OUT_SIZE], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x)
    *p1++ = '0';
  if (x < 0)
    *o++ = '-', x = -x;
  while (x)
    *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf)
    *o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(ll x) {
  static char buf[25];
  char *p1 = buf;
  if (!x)
    *p1++ = '0';
  if (x < 0)
    *o++ = '-', x = -x;
  while (x)
    *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf)
    *o++ = *p1;
}
inline void println1(ll x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) {
  while (*s)
    *o++ = *s++;
}
inline void println1(char *s) {
  print1(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out) {
    if (*(o - 1) == '\n')
      *--o = 0;
    puts(Out);
  }
}
struct puts_write {
  ~puts_write() { flush1(); }
} _puts;
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(ll x) {
#ifdef _WIN32
  printf("%I64d", x);
#else
#ifdef __linux
  printf("%lld", x);
#else
  puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
// #undef ll
#undef OUT_SIZE
#undef BUF_SIZE
}; // namespace fastIO_hqz
using namespace fastIO_hqz;
#define gn read
#define gs read
#define gc read

int main() {
  // files1;
  fast_io;

  const int maxnsmallblock = 10000;
  auto when_smallblock = [&](int n, int m, int z) {
    return 1ll * n * z <= 1e10 || n <= 2 * maxnsmallblock;
  };

  bool testing_speed = false;
  if (testing_speed) {
    assert(RAND_MAX == INT_MAX);
    const ll maxProd = 10000000000000000ll;
    vector<int> cands = {(int)1e4, (int)2e4,(int)5e4, (int)1e5, (int)5e5, (int)1e6};
    for (int n : cands) {
      for (int m : cands) {
        ll z = maxProd / n / m;
        if (z == 0) {
          continue;
        }
        if (z > cands.back()) {
          continue;
        }

        cout << n << ' ' << m << ' ' << z << endl;

        bool choosing_small_block = when_smallblock(n, m, z);
        cout << (choosing_small_block ? "CHOSING SMALL BLOCK" : "CHOSING LARGE BLOCK") << endl;

        start_time = clock();
        vector<int> a;
        vector<tuple<int, int, int>> queries;
        gen_test(n, m, z, a, queries);

        auto res1 = vechash(solveLARGEBLOCK(n, m, z, a, queries));
        auto time_solve_large = (ld)(clock() - start_time) / CLOCKS_PER_SEC;

        start_time = clock();
        auto res2 = vechash(solveSMALLBLOCK(n, m, z, a, queries));
        auto time_solve_small = (ld)(clock() - start_time) / CLOCKS_PER_SEC;

        cout << "Time solve large: " << time_solve_large << endl;
        cout << "Time solve small: " << time_solve_small << endl;

        if (choosing_small_block && time_solve_small > time_solve_large) {
          cout << "\t\tIncorrect choice of block size!!!!!!" << endl;
        }
        if (!choosing_small_block && time_solve_small < time_solve_large) {
          cout << "\t\tIncorrect choice of block size!!!!!!" << endl;
        }
      }
    }
    return 0;
  }

  int n, m, z;

  read(n);
  read(m);
  read(z);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    read(a[i]);
  }

  vector<tuple<int, int, int>> queries(m + z);
  for (int i = 0; i < m + z; i++) {
    read(get<0>(queries[i]));
    read(get<1>(queries[i]));
    read(get<2>(queries[i]));
    --get<1>(queries[i]);
  }

  vector<ll> ans;

  if (when_smallblock(n, m, z)) {
    ans = solveSMALLBLOCK(n, m, z, a, queries);
  } else {
    ans = solveLARGEBLOCK(n, m, z, a, queries);
  }

  for (auto x : ans) {
    println(x);
  }
  return 0;
}