#include struct FastI { char buf[1000000]; char *ptr = buf, *end; void read_() { end = (ptr = buf) + fread(buf, 1, sizeof(buf) - 1, stdin); } FastI () { read_(); } void inc() { if (++ptr == end) read_(); } template value_t read() { bool neg = false; value_t res = 0; while ((*ptr < '0' || *ptr > '9') && *ptr != '-') inc(); if (*ptr == '-') neg = true, inc(); while (*ptr >= '0' && *ptr <= '9') res = res * 10 + *ptr - '0', inc(); return neg ? -res : res; } } fasti; #define ri fasti.read #define rs64 fasti.read struct FastO { char buf[1000000]; char *ptr = buf; void write_() { fwrite(buf, 1, ptr - buf, stdout); ptr = buf; } ~FastO () { write_(); } void print(char c) { *ptr = c; if (++ptr == std::end(buf)) write_(); } void print(const std::string &s) { for (auto c : s) print(c); } template auto print(str_t s) -> decltype(std::string(s), void()) { print(std::string(s)); } template typename std::enable_if_t::value> print(value_t val) { static char tmp_buf[32]; if (val < 0) print('-'), val = -val; char *head = std::end(tmp_buf); if (val == 0) *--head = '0'; else while (val) *--head = '0' + val % 10, val /= 10; int size = std::end(tmp_buf) - head; if (std::end(buf) - ptr <= size) write_(); memcpy(ptr, head, size); ptr += size; } template void print(A a, B... b) { print(a); print(b...); } template void println(A... a) { print(a..., '\n'); } } fasto; #define print fasto.print #define println fasto.println template struct BIT { int n; value_t all_sum = 0; std::vector data; BIT (int n) : n(n), data(n + 1) {} template BIT (const std::vector &a) : n(a.size()), data(n + 1) { std::copy(a.begin(), a.end(), data.begin() + 1); all_sum = std::accumulate(a.begin(), a.end(), (value_t) 0); for (int i = 1; i < n; i++) if (i + (i & -i) <= n) data[i + (i & -i)] += data[i]; } void add(int i, value_t val) { for (i++; i <= n; i += i & -i) data[i] += val; all_sum += val; } value_t sum(int r) { value_t res = 0; for (; r; r -= r & -r) res += data[r]; return res; } value_t sum(int l, int r) { return sum(r) - sum(l); } value_t sum_right(int l) { return all_sum - sum(l); } }; int main() { int n = ri(); int q = ri(); std::vector a(n); std::vector > p(n); for (int i = 0; i < n; i++) { a[i] = ri(); p[i] = {a[i], i}; } std::sort(p.begin(), p.end()); int head = n - 1; struct Query { int l; int r; int x; int id; }; std::pair qinfo[q]; std::pair qs[q]; for (int i = 0; i < q; i++) { qinfo[i].first = ri() - 1; qinfo[i].second = ri(); qs[i].first = ri(); qs[i].second = i; } std::sort(qs, qs + q, [] (auto &i, auto &j) { return i.first > j.first; }); BIT tree(a); std::vector res(q); for (auto &i : qs) { while (head >= 0 && p[head].first >= i.first) { tree.add(p[head].second, 100000000000001 - a[p[head].second]); head--; } auto tmp = tree.sum(qinfo[i.second].first, qinfo[i.second].second); res[i.second] = (int64_t) i.first * (tmp / 100000000000001ULL) + tmp % 100000000000001ULL; } for (auto i : res) println(i); return 0; }