/**
 * @author n685
 * @brief
 * @date 2024-10-04 14:21:21
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

struct Fenwick {
  using T = int64_t;
  using U = int;
  int sz;
  std::vector<T> val;
  static T comb(T a, T b) { return a + b; }
  static T inv(T a) { return -a; }
  Fenwick() : sz(0) {}
  explicit Fenwick(int _sz) : sz(_sz), val(sz + 1) {}
  void upd(int i, T a) {
    i++;
    for (; i <= sz; i += (i & -i)) {
      val[i] = comb(val[i], a);
    }
  }
  void upd(int i, int j, U a) {
    upd(i, a);
    if (j < sz) {
      upd(j + 1, inv(a));
    }
  }
  U sum(int i) const {
    i++;
    T ans{0};
    for (; i > 0; i -= (i & -i)) {
      ans = comb(ans, val[i]);
    }
    return static_cast<U>(ans);
  }
#ifdef LOCAL
  auto debug() {
    return rv::iota(0, sz) | rv::transform([&](int ind) { return sum(ind); });
  }
#else
  void debug() {}
#endif
};

struct LL {
  int l{-1}, r{-1};
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int n, q;
  std::cin >> n >> q;

  std::vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    char c;
    std::cin >> c;
    s[i] = c - '0';
  }
  std::vector<std::vector<std::tuple<int, int, int>>> queries(n + 1);
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    std::cin >> l >> r >> k;
    --l;
    --r;
    queries[k].emplace_back(l, r, i);
  }
  std::vector<LL> ll(n);
  for (int i = 0; i < n; ++i) {
    if (i > 0) {
      ll[i].l = i - 1;
    }
    if (i < n - 1) {
      ll[i].r = i + 1;
    }
  }
  Fenwick li(n), ri(n);
  for (int i = 0; i < n; ++i) {
    li.upd(i, i, i);
    ri.upd(i, i, i);
  }
  std::vector<int> del, ndel;
  for (int i = 0; i < n; ++i) {
    if (i == 0 || s[i] != s[i - 1]) {
      del.push_back(i);
    }
  }
  int fi = 0;
  std::vector<int> ans(q);
  for (int i = 0; i <= n; ++i) {
    dbg(li.debug());
    dbg(ri.debug());
    for (auto [l, r, ind] : queries[i]) {
      ans[ind] = std::max(0, ri.sum(r) - li.sum(l) + 1);
    }
    if (i == n) {
      break;
    }
    int pre = -1;
    for (int j = 0; j < std::ssize(del); ++j) {
      int nxt = ll[del[j]].r;
      if (j == std::ssize(del) - 1 || (del[j + 1] != nxt && s[nxt] != pre)) {
        ndel.push_back(nxt);
      }
    }
    li.upd(0, n, 1);
    for (int j = 0; j < std::ssize(del); ++j) {
      if (fi == del[j]) {
        fi = ll[del[j]].r;
      }
      if (ll[del[j]].l != -1) {
        ll[ll[del[j]].l].r = ll[del[j]].r;
      }
      if (ll[del[j]].r != -1) {
        ll[ll[del[j]].r].l = ll[del[j]].l;
      }
      li.upd(del[j], n, -1);
      ri.upd(del[j], n, -1);
    }
  }
  for (int i : ans) {
    std::cout << i << '\n';
  }
}