#include "atcoder/fenwicktree.hpp" #include #include using namespace std; using isize = size_t; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using f64 = long double; using p2 = pair; using el = tuple; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) { res = res * t; } t = t * t; n >>= 1; } return res; } i64 pow(i64 x, i64 n, i64 m) { i64 res = 1; i64 t = x % m; while (n > 0) { if (n & 1) { res = res * t % m; } t = t * t % m; n >>= 1; } return res; } void _main() { i64 n, q; cin >> n >> q; string s; cin >> s; vector> idx(10); for (i64 i = 0; i < n; i++) { idx[s[i] - '0'].push_back(i); } for (;q--;) { i64 l, r; cin >> l >> r; l--; if (r - l <= 3) { i64 ans = 1e18; vector p; for (i64 i = l; i < r; i++) { p.push_back(i - l); } do { i64 x = 0; for (i64 i = 0; i < p.size(); i++) { x = x * 10 + s[p[i]] - '0'; } if (x % 8 != 0) continue; atcoder::fenwick_tree bit(p.size()); i64 sum = 0; for (i64 i = 0; i < p.size(); i++) { sum += bit.sum(p[i], p.size()); bit.add(p[i], 1); } ans = min(ans, sum); } while (next_permutation(p.begin(), p.end())); if (ans == 1e18) { cout << "-1\n"; } else { cout << ans << "\n"; } continue; } vector lim(10, n); for (i64 i = 0; i < 10; i++) { lim[i] = lower_bound(idx[i].begin(), idx[i].end(), r) - idx[i].begin(); } vector cnt(10, 0); i64 ans = 1e18; for (i64 i = 0; i < 1000; i++) { if (i % 8 != 0) continue; string t = to_string(i); if (t.size() != 3) continue; bool ok = true; vector v; for (i64 j = t.size() - 1; j >= 0; j--) { i64 x = t[j] - '0'; i64 k = lim[x] - cnt[x] - 1; if (k < 0 || idx[x][k] < l) { ok = false; } else { v.push_back({idx[x][k], j}); } cnt[x]++; } for (i64 j = t.size() - 1; j >= 0; j--) { i64 x = t[j] - '0'; cnt[x]--; } if (!ok) continue; i64 sum = 0; sort(v.begin(), v.end()); for (i64 j = 0; j < v.size(); j++) { sum += r - v[j].first - 1 - (v.size() - j - 1); } sort(v.begin(), v.end(), [&](p2 a, p2 b){return a.second < b.second;}); if (v.size() >= 2 && v[0].first > v[1].first) sum++; if (v.size() >= 3 && v[1].first > v[2].first) sum++; if (v.size() >= 3 && v[0].first > v[2].first) sum++; ans = min(ans, sum); } cout << (ans == 1e18 ? -1 : ans) << "\n"; } }