#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;
struct Seg{
struct Info {
int cost = 0;
int mx = -1;
};
int s, e,m;
Seg *l, *r;
Info info;
Info merge(const Info &l, const Info &r, int rl, int rr) {
Info c{};
c.cost = max(l.cost, r.cost);
c.mx = max(l.mx, r.mx);
if (l.mx != -1) {
// LAST in r less than l_max
// call another st
int r_max_lt = seg2->max_lt(rl, rr, l.mx);
if (r_max_lt != -1) {
c.cost = max(c.cost, l.mx + r_max_lt);
}
}
return c;
}
Seg (int s, int e, vector<int> &a) {
this->s = s;this->e = e;
m=(s+e)/2;
if (s!=e) {
l = new Seg(s,m, a);
r = new Seg(m+1, e, a);
info = merge(l->info, r->info, r->s, r->e);
} else {
info = Info{};
info.mx = a[s];
}
}
Info query(int x, int y) {
if (x <= s && e <= y) {
return info;
}
if (y < s || e < x) {
return Info{};
}
if (x > m) return r->query(x,y);
if (y < m) return l->query(x,y);
int rl = max(r->s, x);
int rr = min(r->e, y);
return merge(l->query(x,y), r->query(rl,rr), rl, rr);
}
};
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]);
Seg seg(0, n-1, a);
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";
}
}
