#include<bits/stdc++.h>
using namespace std;
#define DEBUG 0
#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
#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>;
}
struct Seg{
struct Info {
int cost = 0;
vector<int> vals;
};
int s, e,m;
Seg *l, *r;
Info info;
Info merge(const Info &l, const Info &r) {
dbg_c(l.vals);
dbg_c(r.vals);
Info c{};
c.cost = max(l.cost, r.cost);
if (!l.vals.empty()) {
int l_max = l.vals.back();
// LAST in r less than or equal to l_max
// proxy: first in r that is > l_max with ub
// and then -1
auto it = std::upper_bound(r.vals.begin(), r.vals.end(), l_max);
if (it != r.vals.begin()) {
it--;
printf("l_max=%d, *it=%d\n", l_max, *it);
c.cost = max(c.cost, l_max + *it);
}
}
std::merge(l.vals.begin(), l.vals.end(), r.vals.begin(), r.vals.end(), std::back_inserter(c.vals));
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);
} else {
info = Info{};
info.vals.push_back(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);
return merge(l->query(x,y), r->query(x,y));
}
};
signed main() {
int n,m;cin>>n>>m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin>>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";
}
}
