#include <bits/stdc++.h> using namespace std; int main() { int N, Q; string S; cin >> N >> Q >> S; vector<int> cum0(N + 1, 0), cum1(N + 1, 0); for (int i = 0; i < N; i++) { cum0.at(i + 1) = cum0.at(i); cum1.at(i + 1) = cum1.at(i); if (S.at(i) == '0') cum0.at(i + 1)++; else cum1.at(i + 1)++; } while (Q--) { int L, R, K; cin >> L >> R >> K; L--, R--; bool ok = false; int len = 1; for (int i = L + 1; i <= R; i++) { if (S[i - 1] != S[i]) len = 1; else { len++; if (len >= K) { ok = true; break; } } } if (!ok) { cout << R - L + 1 << endl; continue; } int x = cum0.at(R + 1) - cum0.at(L); int y = cum1.at(R + 1) - cum1.at(L); int z = (x - y) % (2 * K - 1); if (z < 0) z += 2 * K - 1; cout << max(z - 1, 2 * K - 2 - z) << endl; } }