#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// 0 for null
namespace seg {
constexpr int MAX_NUM_NODES = 1 << 26;
int n, id, ls[MAX_NUM_NODES], rs[MAX_NUM_NODES];
int sum0s[MAX_NUM_NODES];
Int sum1s[MAX_NUM_NODES];
void init(int n_) {
  n = n_;
  id = 1;
}
int newNode() {
  assert(id < MAX_NUM_NODES);
  const int u = id++;
  ls[u] = rs[u] = 0;
  sum0s[u] = 0;
  sum1s[u] = 0;
  return u;
}
int build(int l, int r) {
  const int u = newNode();
  if (l + 1 == r) return u;
  const int mid = (l + r) / 2;
  ls[u] = build(l, mid);
  rs[u] = build(mid, r);
  return u;
}
int modify(int u, int l, int r, int pos, Int val) {
  if (!(l <= pos && pos < r)) return u;
  const int v = newNode();
  if (l + 1 == r) {
    sum0s[v] = 1;
    sum1s[v] = val;
    return v;
  }
  const int mid = (l + r) / 2;
  ls[v] = modify(ls[u], l, mid, pos, val);
  rs[v] = modify(rs[u], mid, r, pos, val);
  sum0s[v] = sum0s[ls[v]] + sum0s[rs[v]];
  sum1s[v] = sum1s[ls[v]] + sum1s[rs[v]];
  return v;
}
int modify(int u, int pos, Int val) {
  return modify(u, 0, n, pos, val);
}
Int get1(int u, int l, int r, int a, int b) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return sum1s[u];
  const int mid = (l + r) / 2;
  return get1(ls[u], l, mid, a, b) + get1(rs[u], mid, r, a, b);
}
Int get1(int u, int a, int b) {
  return get1(u, 0, n, a, b);
}
int find0(int u, int v, int l, int r, int k) {
  if (l + 1 == r) return r;
  const int mid = (l + r) / 2;
  const int kL = sum0s[ls[v]] - sum0s[ls[u]];
  return (kL >= k) ? find0(ls[u], ls[v], l, mid, k) : find0(rs[u], rs[v], mid, r, k - kL);
}
int find0(int u, int v, int k) {
  if (0 >= k) return 0;
  assert(sum0s[v] - sum0s[u] >= k);
  return find0(u, v, 0, n, k);
}
}  // seg


int N;
vector<Int> A;

Int brute(int L, int R, int K) {
  assert(0 <= K); assert(K <= R - L);
  vector<Int> as(A.begin() + L, A.begin() + R);
  sort(as.begin(), as.end());
  Int ret = 0;
  for (int i = 0; i < K; ++i) ret += as[i];
  return ret;
}

vector<int> segs;
void init() {
  vector<pair<Int, int>> ais(N);
  for (int i = 0; i < N; ++i) ais[i] = make_pair(A[i], i);
  sort(ais.begin(), ais.end());
// cerr<<"ais = "<<ais<<endl;
  vector<int> poss(N, -1);
  for (int j = 0; j < N; ++j) poss[ais[j].second] = j;
  segs.assign(N + 1, 0);
  seg::init(N);
  segs[0] = seg::build(0, N);
  for (int i = 0; i < N; ++i) {
    segs[i + 1] = seg::modify(segs[i], poss[i], A[i]);
  }
// for(int i=0;i<=N;++i){cerr<<"segs["<<i<<"]: ";for(int j=0;j<N;++j)cerr<<seg::get1(segs[i],j,j+1)<<" ";cerr<<endl;}
cerr<<"seg::id = "<<seg::id<<endl;
}
Int solve(int L, int R, int K) {
  assert(0 <= K); assert(K <= R - L);
  if (K == 0) return 0;
  const int pos = seg::find0(segs[L], segs[R], K);
// cerr<<L<<" "<<R<<" "<<K<<": pos = "<<pos<<endl;
  Int ret = 0;
  ret += seg::get1(segs[R], 0, pos);
  ret -= seg::get1(segs[L], 0, pos);
  return ret;
}

int main() {
  int ID, Q;
  for (; ~scanf("%d", &ID); ) {
    scanf("%d%d", &N, &Q);
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    
    init();
    
    for (; Q--; ) {
      int L, R, K, X, Y;
      scanf("%d%d%d%d%d", &L, &R, &K, &X, &Y);
      --L;
      --X;
      Int ans = 0;
      ans += solve(L, min(L + Y + K, R), Y);
      ans -= solve(L, min(L + X + K, R), X);
      printf("%lld\n", ans);
    }
  }
  return 0;
}