#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0;
  bool f = 1;
  char s = getchar();
  while ((s < '0' || s > '9') && s > 0) {
    if (s == '-') f ^= 1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') x = (x << 1) + (x << 3) + s - '0', s = getchar();
  return f ? x : -x;
}
int n, q, a[20105], st[20105][20], dp[20105][20][35], lg[20105];
int A[35], B[35], tmp[35];
inline int maxx(int x, int y) { return x + a[x] > y + a[y] ? x : y; }
inline int rmq(int l, int r) {
  if (l > r) return 0;
  int k = lg[r - l + 1];
  return maxx(st[l][k], st[r - (1 << k) + 1][k]);
}
signed main() {
  n = read(), q = read();
  for (int i = 1; i <= n; i++) a[i] = read(), st[i][0] = i;
  for (int i = 0; i <= 15; i++)
    if ((1 << i) <= n + 30) lg[(1 << i)] = i;
  for (int i = 3; i <= n + 30; i++)
    if (lg[i] == 0) lg[i] = lg[i - 1];
  for (int i = n; i > 0; i--)
    for (int j = 1; i + (1 << j) - 1 <= n; j++)
      st[i][j] = maxx(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  for (int i = 1; i <= n; i++)
    for (int k = 0; k <= 30; k++) dp[i][0][k] = i + a[i] + k;
  for (int j = 0; j < 15; j++) {
    for (int i = 1; i <= n; i++)
      for (int k = 0; k <= 30; k++)
        for (int l = k; l <= k; l++) {
          dp[i][j + 1][l] =
              max(dp[i][j + 1][l], dp[rmq(i, dp[i][k][j])][j][l - k]);
          dp[i][j + 1][l] = max(dp[i][j + 1][l], dp[i][j + 1][k] + l - k);
        }
  }
  while (q--) {
    int l = read(), r = read(), k = read();
    if (l == r) {
      printf("0\n");
      continue;
    }
    if (r <= l + a[l] + k) {
      printf("1\n");
      continue;
    }
    int ans = 2;
    for (int i = 0; i <= k; i++) A[i] = l + a[l] + i;
    for (int e = lg[r - l + 1]; e >= 0; e--) {
      for (int i = 0; i <= k; i++) tmp[i] = A[i], B[i] = rmq(l, A[i]);
      bool off = 0;
      for (int i = 0; i <= k && !off; i++)
        for (int j = i; j <= k && !off; j++)
          if (dp[B[i]][e][j - i] > tmp[j]) {
            tmp[j] = dp[B[i]][e][j - i];
            if (tmp[j] >= r) off = 1;
          }
      if (off) continue;
      ans += (1 << e);
      printf("%d %d\n", e, ans);
      for (int i = 0; i <= k; i++) A[i] = tmp[i];
    }
    printf("%d\n", ans);
  }
  return 0;
}
