#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// usage: order_of_key(x): # elements < x. find_by_order(k): k-th smallest (0-indexed)
// IMPORTANT: ordered_multiset find() doesnt work. use find_by_order(order_of_key(x)). also, lb and ub are swapped (lb returns first >x).
namespace pbds {
using namespace __gnu_pbds;
template <class K,class V> using hash_map = gp_hash_table<K,V>;
template <class K> using ordered_set = tree<K,null_type,std::less<K>,rb_tree_tag,tree_order_statistics_node_update>;
template <class K> using ordered_multiset = tree<K,null_type,std::less_equal<K>,rb_tree_tag,tree_order_statistics_node_update>;
}
#define int long long
#define DEBUG 1
#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);
} else {
info = Info{};
}
}
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 (s==e) {
return (info.mx < t) ? info.mx : -1;
}
if (info.mn >= t) return -1;
if (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);
int L = l->max_lt(x,y, t);
int R = r->max_lt(x,y, t);
return max(L,R);
}
} *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() {
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";
}
}
