/**
 * @author n685
 * @brief
 * @date 2024-10-05 17:09:37
 *
 *
 */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T>
using ISet = tree<
  T,
  null_type,
  std::less<T>,
  rb_tree_tag,
  tree_order_statistics_node_update>;

#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) {
    if (i > j) {
      return;
    }
    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() const {
    // return rv::iota(0, sz) | rv::transform([&](int ind) { return sum(ind);
    // });
    std::vector<int> ans;
    ans.reserve(sz);
    for (int i = 0; i < sz; ++i) {
      ans.push_back(sum(i));
    }
    return ans;
  }
#else
  void debug() {}
#endif
};

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);
  }
  Fenwick li(n);
  for (int i = 0; i < n; ++i) {
    li.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);
    }
  }
  ISet<int> vals;
  for (int i = 0; i < n; ++i) {
    vals.insert(i);
  }
  int fi = 0;
  std::vector<int> ans(q);
  for (int i = 0; i <= n; ++i) {
    dbg(i);
    dbg(li.debug());
    nline();
    for (auto [l, r, ind] : queries[i]) {
      ans[ind]
        = std::max(0, static_cast<int>(vals.order_of_key(r + 1)) - li.sum(l));
    }
    if (vals.empty()) {
      continue;
    }
    if (i == n) {
      break;
    }
    int pre = -1;
    for (int j = 0; j < std::ssize(del); ++j) {
      // int nxt = ll[del[j]].r;
      auto it = vals.upper_bound(del[j]);
      if (it == vals.end()) {
        continue;
      }
      int nxt = *it;
      if (j == std::ssize(del) - 1 || (del[j + 1] != nxt && s[nxt] != pre)) {
        ndel.push_back(nxt);
      }
    }
    li.upd(fi, n, 1);
    for (int j = 0; j < std::ssize(del); ++j) {
      if (fi == del[j]) {
        auto it = vals.upper_bound(del[j]);
        if (it == vals.end()) {
          fi = n;
        } else {
          fi = *it;
        }
      }
      li.upd(del[j], n, -1);
      vals.erase(del[j]);
    }
    std::swap(ndel, del);
    ndel.clear();
  }
  for (int i : ans) {
    std::cout << i << '\n';
  }
}