#define DEBUG 0
#if (!DEBUG)
#pragma GCC optimize("O3,unroll-loops")
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define printf if(DEBUG) printf
#define cerr if(DEBUG) cerr
template <typename T>
void print(const T& c) {
for (const auto& e : c) {
cerr << e << " ";
} cerr << '\n';
}
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << endl
#define dbg_c(v) cerr << #v << " : "; print(v)
#else
#define dbg(x)
#define dbg_c(v)
#endif
vector<int> a;
struct Seg2{
struct Info {
int mn = INT_MAX;
int mx = -INT_MAX;
};
int s, e,m;
Seg2 *l, *r;
Info info;
Info merge(const Info &l, const Info &r) {
Info c{};
c.mn = min(l.mn, r.mn);
c.mx = max(l.mx, r.mx);
return c;
}
Seg2 (int s, int e) {
this->s = s;this->e = e;
m=(s+e)/2;
if (s!=e) {
l = new Seg2(s,m);
r = new Seg2(m+1, e);
}
}
void set(int x, int v) {
if (s == e) {
info.mn = info.mx = v; return;
}
if (x <= m) l->set(x, v);
else r->set(x, v);
info = merge(l->info, r->info);
}
int max_lt(int x, int y, int t) {
if (y < s || e < x) return -1;
if (info.mn >= t) return -1;
if ((x <= s && e <= y) && (info.mx < t)) return info.mx;
if (x > m) return r->max_lt(x,y,t);
if (y <= m) return l->max_lt(x,y,t);
return max(l->max_lt(x,y,t), r->max_lt(x,y,t));
}
} *seg2;
template <class T, class F>
struct StaticRangeQuery {
int n=0;
vector<vector<T>> st;
F fn;
StaticRangeQuery() = default;
StaticRangeQuery(F f): fn(std::move(f)) {}
StaticRangeQuery(const vector<T>& a, F f): fn(std::move(f)) { build(a); }
void build(const vector<T>& a) {
n = (int)a.size();
if (!n) { st.clear(); return; }
int L = 1;
while ((1LL << (L - 1)) < n) L++;
st.assign(L, vector<T>(n));
st[0] = a;
for (int k=1;k<L;k++) {
int half = 1 << (k - 1), block = half << 1;
for (int l=0;l<n;l+=block) {
int m = min(n, l + half), r = min(n, l + block);
st[k][m - 1] = a[m - 1];
for (int i=m - 2;i>=l;i--) st[k][i] = fn(a[i], st[k][i + 1]);
if (m == r) continue;
st[k][m] = a[m];
for (int i=m + 1;i<r;i++) st[k][i] = fn(st[k][i - 1], a[i]);
}
}
}
int size() const { return n; }
const T& get(int i) const { return st[0][i]; }
T query(int l, int r) const {
if (l == r) return st[0][l];
int k = 31 - __builtin_clz(l ^ r) + 1;
return fn(st[k][l], st[k][r]);
}
};
template <class T, class F>
StaticRangeQuery(const vector<T>&, F) -> StaticRangeQuery<T, F>;
struct Info {
int cost = 0;
int mx = -1;
int s, e;
};
Info merge(const Info &l, const Info &r) {
Info c{};
c.cost = max(l.cost, r.cost);
c.mx = max(l.mx, r.mx);
c.s = l.s; c.e = r.e;
if (l.mx != -1) {
// LAST in r less than l_max
// call another st
int r_max_lt = seg2->max_lt(r.s, r.e, l.mx);
if (r_max_lt != -1) {
c.cost = max(c.cost, l.mx + r_max_lt);
}
}
return c;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n,m;cin>>n>>m;
a.resize(n);
for (int i = 0; i < n; i++) cin>>a[i];
seg2 = new Seg2(0, n-1);
for (int i = 0; i < n; i++) seg2->set(i, a[i]);
vector<Info> b(n);
for (int i = 0; i < n; i++) {
b[i] = Info{0, a[i], i, i};
}
auto seg = StaticRangeQuery(b, ::merge);
for (int i = 0; i < m; i++) {
int l,r,k;cin>>l>>r>>k; l--,r--;
auto q = seg.query(l,r);
printf("cost %d\n",q.cost);
cout<<(q.cost <= k ? 1 : 0)<<"\n";
}
}
