Problem: <image>

William really wants to get a pet. Since his childhood he dreamt about getting a pet grasshopper. William is being very responsible about choosing his pet, so he wants to set up a trial for the grasshopper!

The trial takes place on an array a of length n, which defines lengths of hops for each of n cells. A grasshopper can hop around the sells according to the following rule: from a cell with index i it can jump to any cell with indices from i to i+a_i inclusive.

Let's call the k-grasshopper value of some array the smallest number of hops it would take a grasshopper to hop from the first cell to the last, but before starting you can select no more than k cells and remove them from the array. When a cell is removed all other cells are renumbered but the values of a_i for each cell remains the same. During this the first and the last cells may not be removed.

It is required to process q queries of the following format: you are given three numbers l, r, k. You are required to find the k-grasshopper value for an array, which is a subarray of the array a with elements from l to r inclusive.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 20000), the length of the array and the number of queries respectively.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) – the elements of the array.

The following q lines contain queries: each line contains three integers l, r and k (1 ≤ l ≤ r ≤ n, 0 ≤ k ≤ min(30, r-l)), which are the edges of the subarray and the number of the grasshopper value respectively.

Output

For each query print a single number in a new line — the response to a query.

Example

Input


9 5
1 1 2 1 3 1 2 1 1
1 1 0
2 5 1
5 9 1
2 8 2
1 9 4


Output


0
2
1
2
2

Note

For the second query the process occurs like this: <image>

For the third query the process occurs like this: <image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

template <typename T, int NDIMS> struct tensor_view {
	static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
	std::array<int, NDIMS> shape;
	std::array<int, NDIMS> strides;
	T* data;

	tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_, T* data_) : shape(shape_), strides(strides_), data(data_) {}

public:
	tensor_view() : shape{0}, strides{0}, data(nullptr) {}

protected:
	int flatten_index(std::array<int, NDIMS> idx) const {
		int res = 0;
		for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
		return res;
	}
	int flatten_index_checked(std::array<int, NDIMS> idx) const {
		int res = 0;
		for (int i = 0; i < NDIMS; i++) {
			assert(0 <= idx[i] && idx[i] < shape[i]);
			res += idx[i] * strides[i];
		}
		return res;
	}

public:
	T& operator[] (std::array<int, NDIMS> idx) const {
		return data[flatten_index(idx)];
	}
	T& at(std::array<int, NDIMS> idx) const {
		return data[flatten_index_checked(idx)];
	}

	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) const {
		std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1, shape.end(), nshape.begin());
		std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1, strides.end(), nstrides.begin());
		T* ndata = data + (strides[0] * idx);
		return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
	}
	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) const {
		assert(0 <= idx && idx < shape[0]);
		return operator[](idx);
	}

	template <int D = NDIMS>
	typename std::enable_if<(0 == D), T&>::type operator * () const {
		return *data;
	}

	template <typename U, int D> friend struct tensor_view;
	template <typename U, int D> friend struct tensor;
};

template <typename T, int NDIMS> struct tensor {
	static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
	std::array<int, NDIMS> shape;
	std::array<int, NDIMS> strides;
	int len;
	T* data;

public:
	tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}

	explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
		shape = shape_;
		strides[NDIMS-1] = 1;
		for (int i = NDIMS-1; i > 0; i--) {
			strides[i-1] = strides[i] * shape[i];
		}
		len = strides[0] * shape[0];
		data = new T[len];
		std::fill(data, data + len, t);
	}

	tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
		for (int i = 0; i < len; i++) {
			data[i] = o.data[i];
		}
	}

	tensor& operator=(tensor&& o) noexcept {
		using std::swap;
		swap(shape, o.shape);
		swap(strides, o.strides);
		swap(len, o.len);
		swap(data, o.data);
		return *this;
	}
	tensor(tensor&& o) : tensor() {
		*this = std::move(o);
	}
	tensor& operator=(const tensor& o) {
		return *this = tensor(o);
	}
	~tensor() { delete[] data; }

	using view_t = tensor_view<T, NDIMS>;
	view_t view() {
		return tensor_view<T, NDIMS>(shape, strides, data);
	}
	operator view_t() {
		return view();
	}

	using const_view_t = tensor_view<const T, NDIMS>;
	const_view_t view() const {
		return tensor_view<const T, NDIMS>(shape, strides, data);
	}
	operator const_view_t() const {
		return view();
	}

	T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }
	T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
	const T& operator[] (std::array<int, NDIMS> idx) const { return view()[idx]; }
	const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }

	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) {
		return view()[idx];
	}
	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
		return view().at(idx);
	}

	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type operator[] (int idx) const {
		return view()[idx];
	}
	template <int D = NDIMS>
	typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int idx) const {
		return view().at(idx);
	}

	template <int D = NDIMS>
	typename std::enable_if<(0 == D), T&>::type operator * () {
		return *view();
	}
	template <int D = NDIMS>
	typename std::enable_if<(0 == D), const T&>::type operator * () const {
		return *view();
	}
};

template <typename T> void setmax(T& a, T b) { if (b > a) a = b; }

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, Q; cin >> N >> Q;
	vector<int> A(N);
	for (int i = 0; i < N; i++) { cin >> A[i]; A[i] += i; }

	const int MAXK = 30;
	int S = 0;
	while (!((1 << S) >= N)) S++;

	tensor<pair<int, int>, 3> dp({S+1, N, MAXK+1});
	{
		vector<pair<int, int>> stk; stk.reserve(N);
		for (int i = N-1; i >= 0; i--) {
			while (!stk.empty() && A[i] > stk.back().first) stk.pop_back();
			stk.push_back({A[i], i});
			int lo = -1, hi = int(stk.size())-1;
			while (hi - lo > 1) {
				int md = (lo + hi) / 2;
				if (stk[md].second <= A[i]) hi = md;
				else lo = md;
			}
			pair<int, int> cur = stk[hi];
			dp[{0, i, 0}] = cur;
			for (int k = 1; k <= MAXK; k++) {
				if (A[i] + k < N) setmax(cur, {A[A[i]+k], A[i]+k});
				dp[{0, i, k}] = cur;
			}
		}
	}

	for (int s = 1; s <= S; s++) {
		for (int i = 0; i < N; i++) {
			for (int k1 = 0; k1 <= MAXK; k1++) {
				int j = dp[{s-1, i, k1}].second;
				for (int k2 = 0; k1+k2 <= MAXK; k2++) {
					setmax(dp[{s, i, k1+k2}], dp[{s-1, j, k2}]);
				}
			}
		}
	}

	while (Q--) {
		int L, R, K; cin >> L >> R >> K; L--, R--;
		cout << [&]() -> int {
			if (L == R) return 0;
			vector<pair<int, int>> cur(K+1, {A[L], L});
			vector<pair<int, int>> nxt(K+1);
			int resp = 0;
			auto is_done = [&](const vector<pair<int, int>>& v) {
				for (int k = 0; k <= K; k++) {
					if (v[k].first + (K-k) >= R) return true;
				}
				return false;
			};
			if (is_done(cur)) return 1;
			int s = 0;
			while (true) {
				for (int k = 0; k <= K; k++) {
					nxt[k] = dp[{s, L, k}];
				}
				if (is_done(nxt)) {
					break;
				} else {
					resp = (1 << s);
					s++;
					std::swap(nxt, cur);
				}
			}

			if (s) s--;

			while (s) {
				s--;
				std::copy(cur.begin(), cur.end(), nxt.begin());
				for (int k = 0; k <= K; k++) {
					for (int l = 0; l <= K-k; l++) {
						setmax(nxt[l+k], dp[{s, cur[k].second, l}]);
					}
				}
				if (is_done(nxt)) {
					// do nothing
				} else {
					resp += 1 << s;
					std::swap(cur, nxt);
				}
			}
			resp++;
			return resp + 1;
		}() << '\n';
	}

	return 0;
}