/**
 * @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;

// based on https://codeforces.com/blog/entry/18051
template <class T> struct LSeg {
  struct Node {
    using RT = T;
    static constexpr RT ID = 0;
    T val = 0;

    T la = 0;

    Node() = default;
    explicit Node(T v) : val(v) {}

    RT value() const { return val; }
    static RT comb(RT a, RT b) { return std::max(a, b); }
    void add(T v, int /*k*/) {
      val += v;
      la += v;
    }
    void pull(Node &ll, Node &rr) {
      if (la != 0) {
        return;
      }
      val = std::max(ll.val, rr.val);
    }
    void push(Node &ll, Node &rr, int k) {
      if (la == 0) {
        return;
      }
      ll.add(la, k / 2);
      rr.add(la, k / 2);
      la = 0;
    }
  };
  using RT = typename Node::RT;
  int h{}, sz{};
  std::vector<Node> val;

  void push(int l, int r) {
    l += sz, r += sz;
    for (int s = h - 1, k = (1 << (h - 1)); s >= 1; --s, k /= 2) {
      for (int i = (l >> s); i <= (r >> s); ++i) {
        val[i].push(val[2 * i], val[2 * i + 1], k);
      }
    }
  }
  void build(int l, int r) {
    l += sz, r += sz;
    l /= 2, r /= 2;
    for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2) {
      for (int i = l; i <= r; ++i) {
        val[i].pull(val[2 * i], val[2 * i + 1]);
      }
    }
  }

  LSeg() = default;
  explicit LSeg(int _sz)
      // : h((31 - __builtin_clz(2 * sz - 1)) + 2), sz(1 << (h - 1)) {
      : h(std::bit_width<uint32_t>(2 * _sz - 1)),
        sz(1 << (h - 1)) {
    // h = std::__lg(2 * _sz - 1) + 1;
    val.resize(2 * sz);
  }
  explicit LSeg(const std::vector<T> &v) : LSeg(static_cast<int>(v.size())) {
    for (int i = 0; i < static_cast<int>(v.size()); ++i) {
      val[i + sz] = Node(v[i]);
    }
    build(0, sz - 1);
  }

  void upd(int l, int r, const std::function<void(Node &, int)> &f) {
    if (l > r) {
      return;
    }
    push(l, l), push(r, r);

    bool cl = false, cr = false;
    int k = 1;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2, k *= 2) {
      if (cl) {
        val[l - 1].pull(val[2 * l - 2], val[2 * l - 1]);
      }
      if (cr) {
        val[r + 1].pull(val[2 * r + 2], val[2 * r + 3]);
      }
      if (l % 2 == 1) {
        f(val[l++], k), cl = true;
      }
      if (r % 2 == 0) {
        f(val[r--], k), cr = true;
      }
    }
    for (--l, ++r; r >= 1; l /= 2, r /= 2) {
      if (cl && l >= 1) {
        val[l].pull(val[2 * l], val[2 * l + 1]);
      }
      if (cr && (!cl || l != r)) {
        val[r].pull(val[2 * r], val[2 * r + 1]);
      }
    }
  }
  void add(int l, int r, T v) {
    upd(l, r, [&v](Node &n, int k) { n.add(v, k); });
  }
  RT query(int l, int r) {
    if (l > r) {
      return Node::ID;
    }
    push(l, l), push(r, r);

    RT ll = Node::ID, rr = Node::ID;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1) {
        ll = Node::comb(ll, val[l++].value());
      }
      if (r % 2 == 0) {
        rr = Node::comb(val[r--].value(), rr);
      }
    }
    return Node::comb(ll, rr);
  }

  int walk_l(int l, int r, const std::function<bool(const Node &)> &c) {
    if (l > r) {
      return -1;
    }
    push(l, l);
    l += sz;
    if (c(val[l])) {
      return l - sz;
    }

    int ind = -1;
    int s = 1;
    for (; l > 1; l /= 2, s *= 2) {
      if (l % 2 == 0 && c(val[l + 1])) {
        ind = l + 1;
        break;
      }
    }
    if (ind == -1) {
      return -1;
    }

    while (ind < sz) {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind])) {
        ind = 2 * ind;
      } else if (c(val[2 * ind + 1])) {
        ind = 2 * ind + 1;
      } else {
        return -1;
      }
      s /= 2;
    }
    if (c(val[ind]) && ind - sz <= r) {
      return ind - sz;
    }
    return -1;
  }
  int walk_r(int l, int r, const std::function<bool(const Node &)> &c) {
    if (l > r) {
      return -1;
    }
    push(r, r);
    r += sz;
    if (c(val[r])) {
      return r - sz;
    }

    int ind = -1;
    int s = 1;
    for (; r > 1; r /= 2, s *= 2) {
      if (r % 2 == 1 && c(val[r - 1])) {
        ind = r - 1;
        break;
      }
    }
    if (ind == -1) {
      return -1;
    }

    while (ind < sz) {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind + 1])) {
        ind = 2 * ind + 1;
      } else if (c(val[2 * ind])) {
        ind = 2 * ind;
      } else {
        return -1;
      }
      s /= 2;
    }
    if (c(val[ind]) && ind - sz >= l) {
      return ind - sz;
    }
    return -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);
  }
  LSeg<int> li(n);
  for (int i = 0; i < n; ++i) {
    li.add(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(std::vector(vals.begin(), vals.end()));
    nline();
    for (auto [l, r, ind] : queries[i]) {
      ans[ind] = std::max(
        0,
        static_cast<int>(vals.order_of_key(r + 1)) - li.query(l, 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.add(0, n - 1, 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;
        }
      }
      int rank = static_cast<int>(vals.order_of_key(del[j]));
      int ind = li.walk_l(0, n - 1, [&](const LSeg<int>::Node &v) {
        return v.value() > rank;
      });
      if (ind != -1) {
        li.add(ind, n - 1, -1);
      }
      vals.erase(del[j]);
    }
    std::swap(ndel, del);
    ndel.clear();
  }
  for (int i : ans) {
    std::cout << i << '\n';
  }
}