#include <bits/stdc++.h>
using namespace std;
template <typename T>
void __read(T &a) {
  cin >> a;
}
template <typename T, typename... Args>
void __read(T &a, Args &...args) {
  cin >> a;
  __read(args...);
}
constexpr long long M7 = 1000000007;
constexpr long long M9 = 1000000009;
constexpr long long MFFT = 998244353;
constexpr double PI = 3.14159265358979323846;
template <class T>
void outv(const T &a, char d = ' ', bool nl = false) {
  for (auto &x : a) cout << x << d;
  if (nl) cout << '\n';
}
static mt19937_64 rnd(static_cast<unsigned>(
    chrono::steady_clock::now().time_since_epoch().count()));
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr));
struct segtree {
  struct node {
    long long mn = 0;
    long long sm = 0;
    long long add = 0;
    node(long long val = 0) : mn(val), sm(val), add(0){};
    template <class T>
    void apply(int32_t l, int32_t r, const T &ext) {
      if (ext == 0) return;
      mn = ext;
      sm = ext * (r - l + 1);
      add = ext;
    }
  };
  vector<node> tree;
  long long sz;
  inline node unite(const node &a, const node &b) {
    node res;
    res.mn = min(a.mn, b.mn);
    res.sm = a.sm + b.sm;
    return res;
  }
  inline void push(int32_t pos, int32_t rpos, int32_t l, int32_t r) {
    int32_t mid = (l + r) / 2;
    tree[pos + 1].apply(l, mid, tree[pos].add);
    tree[rpos].apply(mid + 1, r, tree[pos].add);
    tree[pos].add = 0;
  }
  inline void up(int32_t pos, int32_t rpos) {
    tree[pos] = unite(tree[pos + 1], tree[rpos]);
  }
  void build(int32_t pos, int32_t l, int32_t r) {
    if (l != r) {
      int32_t mid = (l + r) / 2;
      int32_t rpos = pos + (mid - l + 1) * 2;
      build(pos + 1, l, mid);
      build(rpos, mid + 1, r);
      up(pos, rpos);
    }
  }
  template <class TIter>
  void build(int32_t pos, int32_t l, int32_t r, TIter &iter) {
    if (l == r) {
      tree[pos] = node(*iter);
      iter++;
    } else {
      int32_t mid = (l + r) / 2;
      int32_t rpos = pos + (mid - l + 1) * 2;
      build(pos + 1, l, mid, iter);
      build(rpos, mid + 1, r, iter);
      up(pos, rpos);
    }
  }
  segtree(long long sz) {
    this->sz = sz;
    tree.resize(2 * sz - 1);
    build(0, 0, sz - 1);
  }
  template <class TIter>
  segtree(TIter begin, TIter end) {
    sz = distance(begin, end);
    tree.resize(2 * sz - 1);
    build(0, 0, sz - 1, begin);
  }
  node get(int32_t pos, int32_t l, int32_t r, int32_t ind) {
    if (l == r) {
      return tree[pos];
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ind <= mid) {
      return get(pos + 1, l, mid, ind);
    }
    return get(rpos, mid + 1, r, ind);
  }
  node get(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr) {
    if (l >= ql && r <= qr) {
      return tree[pos];
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (qr <= mid) {
      return get(pos + 1, l, mid, ql, qr);
    } else if (ql > mid) {
      return get(rpos, mid + 1, r, ql, qr);
    }
    return unite(get(pos + 1, l, mid, ql, qr), get(rpos, mid + 1, r, ql, qr));
  }
  node get(int32_t ind) {
    assert(0 <= ind && ind < sz);
    return get(0, 0, sz - 1, ind);
  }
  node get(int32_t l, int32_t r) {
    assert(0 <= l && l <= r && r < sz);
    return get(0, 0, sz - 1, l, r);
  }
  void getNodes(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                vector<tuple<int32_t, int32_t, node *>> &res) {
    if (l >= ql && r <= qr) {
      res.emplace_back(l, r, &tree[pos]);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ql <= mid) {
      getNodes(pos + 1, l, mid, ql, qr, res);
    }
    if (qr > mid) {
      getNodes(rpos, mid + 1, r, ql, qr, res);
    }
  }
  vector<tuple<int32_t, int32_t, node *>> getNodes(int32_t l, int32_t r) {
    assert(0 <= l && l <= r && r < sz);
    vector<tuple<int32_t, int32_t, node *>> res;
    getNodes(0, 0, sz - 1, l, r, res);
    return res;
  }
  template <class T>
  void set(int32_t pos, int32_t l, int32_t r, int32_t ind, const T &val) {
    if (l == r) {
      tree[pos] = node(val);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ind <= mid) {
      set(pos + 1, l, mid, ind, val);
    } else {
      set(rpos, mid + 1, r, ind, val);
    }
    up(pos, rpos);
  }
  template <class T>
  void set(int32_t ind, const T &val) {
    assert(0 <= ind && ind < sz);
    set(0, 0, sz - 1, ind, val);
  }
  template <class T>
  void modify(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
              const T &ext) {
    if (l >= ql && r <= qr) {
      tree[pos].apply(l, r, ext);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ql <= mid) {
      modify(pos + 1, l, mid, ql, qr, ext);
    }
    if (qr > mid) {
      modify(rpos, mid + 1, r, ql, qr, ext);
    }
    up(pos, rpos);
  }
  template <class T>
  void modify(int32_t l, int32_t r, const T &ext) {
    assert(0 <= l && l <= r && r < sz);
    modify(0, 0, sz - 1, l, r, ext);
  }
  template <class TFunc>
  int32_t findFirst(int32_t pos, int32_t l, int32_t r, const TFunc &f) {
    if (l == r) {
      return l;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (f(tree[pos + 1])) {
      return findFirst(pos + 1, l, mid, f);
    }
    return findFirst(rpos, mid + 1, r, f);
  }
  template <class TFunc>
  int32_t findFirst(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                    const TFunc &f) {
    if (l >= ql && r <= qr) {
      if (f(tree[pos])) {
        return findFirst(pos, l, r, f);
      }
      return -1;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    int32_t res = -1;
    if (ql <= mid) {
      res = findFirst(pos + 1, l, mid, ql, qr, f);
    }
    if (res == -1 && qr > mid) {
      res = findFirst(rpos, mid + 1, r, ql, qr, f);
    }
    return res;
  }
  template <class TFunc>
  int32_t findFirst(int32_t l, int32_t r, const TFunc &f) {
    assert(0 <= l && l <= r && r < sz);
    return findFirst(0, 0, sz - 1, l, r, f);
  }
  template <class TFunc>
  int32_t findLast(int32_t pos, int32_t l, int32_t r, const TFunc &f) {
    if (l == r) {
      return l;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (f(tree[rpos])) {
      return findLast(rpos, mid + 1, r, f);
    }
    return findLast(pos + 1, l, mid, f);
  }
  template <class TFunc>
  int32_t findLast(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                   const TFunc &f) {
    if (l >= ql && r <= qr) {
      if (f(tree[pos])) {
        return findLast(pos, l, r, f);
      }
      return sz;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    int32_t res = sz;
    if (qr > mid) {
      res = findLast(rpos, mid + 1, r, ql, qr, f);
    }
    if (res == sz && ql <= mid) {
      res = findLast(pos + 1, l, mid, ql, qr, f);
    }
    return res;
  }
  template <class TFunc>
  int32_t findLast(int32_t l, int32_t r, const TFunc &f) {
    assert(0 <= l && l <= r && r < sz);
    return findLast(0, 0, sz - 1, l, r, f);
  }
  void dbg(int32_t pos, int32_t l, int32_t r) {
    if (l == r) {
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    dbg(pos + 1, l, mid);
    dbg(rpos, mid + 1, r);
  }
};
int32_t main() {
  long long n, q, k;
  __read(n, q, k);
  vector<long long> a(n);
  for (auto &v : (a)) cin >> v;
  ;
  vector<pair<long long, long long>> qr(q);
  for (auto &[l, r] : qr) {
    cin >> l >> r;
    l--, r--;
  }
  deque<long long> dq;
  vector<long long> b(n);
  for (long long i = 0; i < n; ++i) {
    while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
    dq.push_back(i);
    if (dq.front() == i - k) dq.pop_front();
    b[i] = a[dq.front()];
  }
  vector<vector<pair<long long, long long>>> c(k);
  for (long long i = 0; i < q; ++i) {
    auto &[l, r] = qr[i];
    c[l % k].emplace_back(l, i);
  }
  segtree st(n + k);
  vector<long long> ans(q);
  for (long long kk = 0; kk < k; ++kk) {
    st.modify(0, n + k - 1, M7);
    long long rem = (n - kk - 1) % k;
    sort(c[rem].begin(), c[rem].end());
    long long ptr = static_cast<long long>(c[rem].size()) - 1;
    for (long long i = n - kk - 1; i >= 0; i -= k) {
      long long pos = st.findFirst(
          i, n + k - 1, [&](const segtree::node &v) { return v.mn < a[i]; });
      st.modify(i, (pos == -1 ? n + k : pos) - 1, a[i]);
      while (ptr >= 0 && c[rem][ptr].first == i) {
        long long ind = c[rem][ptr].second;
        auto &[l, r] = qr[ind];
        long long sz = (r - l + k) / k;
        if (sz > 1) {
          if (sz > 2) {
            ans[ind] = st.get(l + 1, l + (sz - 2) * k).sm;
            ans[ind] /= k;
          }
          ans[ind] += min(a[l + (sz - 1) * k], st.get(l + (sz - 1) * k - 1).mn);
        }
        ans[ind] += a[l];
        ptr--;
      }
      pos = st.findFirst(i, n + k - 1,
                         [&](const segtree::node &v) { return v.mn < b[i]; });
      st.modify(max(0ll, i - k + 1), (pos == -1 ? n + k : pos) - 1, b[i]);
    }
  }
  for (long long i = 0; i < q; ++i) cout << ans[i] << '\n';
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

Students of one unknown college don't have PE courses. That's why q of them decided to visit a gym nearby by themselves. The gym is open for n days and has a ticket system. At the i-th day, the cost of one ticket is equal to a_i. You are free to buy more than one ticket per day.

You can activate a ticket purchased at day i either at day i or any day later. Each activated ticket is valid only for k days. In other words, if you activate ticket at day t, it will be valid only at days t, t + 1, ..., t + k - 1. 

You know that the j-th student wants to visit the gym at each day from l_j to r_j inclusive. Each student will use the following strategy of visiting the gym at any day i (l_j ≤ i ≤ r_j):

  1. person comes to a desk selling tickets placed near the entrance and buy several tickets with cost a_i apiece (possibly, zero tickets); 
  2. if the person has at least one activated and still valid ticket, they just go in. Otherwise, they activate one of tickets purchased today or earlier and go in. 



Note that each student will visit gym only starting l_j, so each student has to buy at least one ticket at day l_j.

Help students to calculate the minimum amount of money they have to spend in order to go to the gym.

Input

The first line contains three integers n, q and k (1 ≤ n, q ≤ 300 000; 1 ≤ k ≤ n) — the number of days, the number of students and the number of days each ticket is still valid. 

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the cost of one ticket at the corresponding day.

Each of the next q lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the segment of days the corresponding student want to visit the gym.

Output

For each student, print the minimum possible amount of money they have to spend in order to go to the gym at desired days.

Example

Input


7 5 2
2 15 6 3 7 5 6
1 2
3 7
5 5
7 7
3 5


Output


2
12
7
6
9

Note

Let's see how each student have to spend their money: 

  * The first student should buy one ticket at day 1. 
  * The second student should buy one ticket at day 3 and two tickets at day 4. Note that student can keep purchased tickets for the next days. 
  * The third student should buy one ticket at day 5. 
  * The fourth student should buy one ticket at day 7. 
  * The fifth student should buy one ticket at day 3 and one at day 4. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void __read(T &a) {
  cin >> a;
}
template <typename T, typename... Args>
void __read(T &a, Args &...args) {
  cin >> a;
  __read(args...);
}
constexpr long long M7 = 1000000007;
constexpr long long M9 = 1000000009;
constexpr long long MFFT = 998244353;
constexpr double PI = 3.14159265358979323846;
template <class T>
void outv(const T &a, char d = ' ', bool nl = false) {
  for (auto &x : a) cout << x << d;
  if (nl) cout << '\n';
}
static mt19937_64 rnd(static_cast<unsigned>(
    chrono::steady_clock::now().time_since_epoch().count()));
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr));
struct segtree {
  struct node {
    long long mn = 0;
    long long sm = 0;
    long long add = 0;
    node(long long val = 0) : mn(val), sm(val), add(0){};
    template <class T>
    void apply(int32_t l, int32_t r, const T &ext) {
      if (ext == 0) return;
      mn = ext;
      sm = ext * (r - l + 1);
      add = ext;
    }
  };
  vector<node> tree;
  long long sz;
  inline node unite(const node &a, const node &b) {
    node res;
    res.mn = min(a.mn, b.mn);
    res.sm = a.sm + b.sm;
    return res;
  }
  inline void push(int32_t pos, int32_t rpos, int32_t l, int32_t r) {
    int32_t mid = (l + r) / 2;
    tree[pos + 1].apply(l, mid, tree[pos].add);
    tree[rpos].apply(mid + 1, r, tree[pos].add);
    tree[pos].add = 0;
  }
  inline void up(int32_t pos, int32_t rpos) {
    tree[pos] = unite(tree[pos + 1], tree[rpos]);
  }
  void build(int32_t pos, int32_t l, int32_t r) {
    if (l != r) {
      int32_t mid = (l + r) / 2;
      int32_t rpos = pos + (mid - l + 1) * 2;
      build(pos + 1, l, mid);
      build(rpos, mid + 1, r);
      up(pos, rpos);
    }
  }
  template <class TIter>
  void build(int32_t pos, int32_t l, int32_t r, TIter &iter) {
    if (l == r) {
      tree[pos] = node(*iter);
      iter++;
    } else {
      int32_t mid = (l + r) / 2;
      int32_t rpos = pos + (mid - l + 1) * 2;
      build(pos + 1, l, mid, iter);
      build(rpos, mid + 1, r, iter);
      up(pos, rpos);
    }
  }
  segtree(long long sz) {
    this->sz = sz;
    tree.resize(2 * sz - 1);
    build(0, 0, sz - 1);
  }
  template <class TIter>
  segtree(TIter begin, TIter end) {
    sz = distance(begin, end);
    tree.resize(2 * sz - 1);
    build(0, 0, sz - 1, begin);
  }
  node get(int32_t pos, int32_t l, int32_t r, int32_t ind) {
    if (l == r) {
      return tree[pos];
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ind <= mid) {
      return get(pos + 1, l, mid, ind);
    }
    return get(rpos, mid + 1, r, ind);
  }
  node get(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr) {
    if (l >= ql && r <= qr) {
      return tree[pos];
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (qr <= mid) {
      return get(pos + 1, l, mid, ql, qr);
    } else if (ql > mid) {
      return get(rpos, mid + 1, r, ql, qr);
    }
    return unite(get(pos + 1, l, mid, ql, qr), get(rpos, mid + 1, r, ql, qr));
  }
  node get(int32_t ind) {
    assert(0 <= ind && ind < sz);
    return get(0, 0, sz - 1, ind);
  }
  node get(int32_t l, int32_t r) {
    assert(0 <= l && l <= r && r < sz);
    return get(0, 0, sz - 1, l, r);
  }
  void getNodes(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                vector<tuple<int32_t, int32_t, node *>> &res) {
    if (l >= ql && r <= qr) {
      res.emplace_back(l, r, &tree[pos]);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ql <= mid) {
      getNodes(pos + 1, l, mid, ql, qr, res);
    }
    if (qr > mid) {
      getNodes(rpos, mid + 1, r, ql, qr, res);
    }
  }
  vector<tuple<int32_t, int32_t, node *>> getNodes(int32_t l, int32_t r) {
    assert(0 <= l && l <= r && r < sz);
    vector<tuple<int32_t, int32_t, node *>> res;
    getNodes(0, 0, sz - 1, l, r, res);
    return res;
  }
  template <class T>
  void set(int32_t pos, int32_t l, int32_t r, int32_t ind, const T &val) {
    if (l == r) {
      tree[pos] = node(val);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ind <= mid) {
      set(pos + 1, l, mid, ind, val);
    } else {
      set(rpos, mid + 1, r, ind, val);
    }
    up(pos, rpos);
  }
  template <class T>
  void set(int32_t ind, const T &val) {
    assert(0 <= ind && ind < sz);
    set(0, 0, sz - 1, ind, val);
  }
  template <class T>
  void modify(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
              const T &ext) {
    if (l >= ql && r <= qr) {
      tree[pos].apply(l, r, ext);
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (ql <= mid) {
      modify(pos + 1, l, mid, ql, qr, ext);
    }
    if (qr > mid) {
      modify(rpos, mid + 1, r, ql, qr, ext);
    }
    up(pos, rpos);
  }
  template <class T>
  void modify(int32_t l, int32_t r, const T &ext) {
    assert(0 <= l && l <= r && r < sz);
    modify(0, 0, sz - 1, l, r, ext);
  }
  template <class TFunc>
  int32_t findFirst(int32_t pos, int32_t l, int32_t r, const TFunc &f) {
    if (l == r) {
      return l;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (f(tree[pos + 1])) {
      return findFirst(pos + 1, l, mid, f);
    }
    return findFirst(rpos, mid + 1, r, f);
  }
  template <class TFunc>
  int32_t findFirst(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                    const TFunc &f) {
    if (l >= ql && r <= qr) {
      if (f(tree[pos])) {
        return findFirst(pos, l, r, f);
      }
      return -1;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    int32_t res = -1;
    if (ql <= mid) {
      res = findFirst(pos + 1, l, mid, ql, qr, f);
    }
    if (res == -1 && qr > mid) {
      res = findFirst(rpos, mid + 1, r, ql, qr, f);
    }
    return res;
  }
  template <class TFunc>
  int32_t findFirst(int32_t l, int32_t r, const TFunc &f) {
    assert(0 <= l && l <= r && r < sz);
    return findFirst(0, 0, sz - 1, l, r, f);
  }
  template <class TFunc>
  int32_t findLast(int32_t pos, int32_t l, int32_t r, const TFunc &f) {
    if (l == r) {
      return l;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    if (f(tree[rpos])) {
      return findLast(rpos, mid + 1, r, f);
    }
    return findLast(pos + 1, l, mid, f);
  }
  template <class TFunc>
  int32_t findLast(int32_t pos, int32_t l, int32_t r, int32_t ql, int32_t qr,
                   const TFunc &f) {
    if (l >= ql && r <= qr) {
      if (f(tree[pos])) {
        return findLast(pos, l, r, f);
      }
      return sz;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    int32_t res = sz;
    if (qr > mid) {
      res = findLast(rpos, mid + 1, r, ql, qr, f);
    }
    if (res == sz && ql <= mid) {
      res = findLast(pos + 1, l, mid, ql, qr, f);
    }
    return res;
  }
  template <class TFunc>
  int32_t findLast(int32_t l, int32_t r, const TFunc &f) {
    assert(0 <= l && l <= r && r < sz);
    return findLast(0, 0, sz - 1, l, r, f);
  }
  void dbg(int32_t pos, int32_t l, int32_t r) {
    if (l == r) {
      return;
    }
    int32_t mid = (l + r) / 2;
    int32_t rpos = pos + (mid - l + 1) * 2;
    push(pos, rpos, l, r);
    dbg(pos + 1, l, mid);
    dbg(rpos, mid + 1, r);
  }
};
int32_t main() {
  long long n, q, k;
  __read(n, q, k);
  vector<long long> a(n);
  for (auto &v : (a)) cin >> v;
  ;
  vector<pair<long long, long long>> qr(q);
  for (auto &[l, r] : qr) {
    cin >> l >> r;
    l--, r--;
  }
  deque<long long> dq;
  vector<long long> b(n);
  for (long long i = 0; i < n; ++i) {
    while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
    dq.push_back(i);
    if (dq.front() == i - k) dq.pop_front();
    b[i] = a[dq.front()];
  }
  vector<vector<pair<long long, long long>>> c(k);
  for (long long i = 0; i < q; ++i) {
    auto &[l, r] = qr[i];
    c[l % k].emplace_back(l, i);
  }
  segtree st(n + k);
  vector<long long> ans(q);
  for (long long kk = 0; kk < k; ++kk) {
    st.modify(0, n + k - 1, M7);
    long long rem = (n - kk - 1) % k;
    sort(c[rem].begin(), c[rem].end());
    long long ptr = static_cast<long long>(c[rem].size()) - 1;
    for (long long i = n - kk - 1; i >= 0; i -= k) {
      long long pos = st.findFirst(
          i, n + k - 1, [&](const segtree::node &v) { return v.mn < a[i]; });
      st.modify(i, (pos == -1 ? n + k : pos) - 1, a[i]);
      while (ptr >= 0 && c[rem][ptr].first == i) {
        long long ind = c[rem][ptr].second;
        auto &[l, r] = qr[ind];
        long long sz = (r - l + k) / k;
        if (sz > 1) {
          if (sz > 2) {
            ans[ind] = st.get(l + 1, l + (sz - 2) * k).sm;
            ans[ind] /= k;
          }
          ans[ind] += min(a[l + (sz - 1) * k], st.get(l + (sz - 1) * k - 1).mn);
        }
        ans[ind] += a[l];
        ptr--;
      }
      pos = st.findFirst(i, n + k - 1,
                         [&](const segtree::node &v) { return v.mn < b[i]; });
      st.modify(max(0ll, i - k + 1), (pos == -1 ? n + k : pos) - 1, b[i]);
    }
  }
  for (long long i = 0; i < q; ++i) cout << ans[i] << '\n';
  return 0;
}

```