Untitled

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

constexpr int maxN = 1e5 + 5;
constexpr int K = 31;
constexpr int MOD = 1e9 + 7;

int fastPow(int base, int power) {
    int result = 1;
    for (; power; power >>= 1) {
        if (power & 1) result = 1LL * result * base % MOD;
        base = 1LL * base * base % MOD;
    }
    return result;
}

vector<int> p(maxN + 1), invp(maxN + 1);

void precalc() {
    p[0] = 1;
    invp[0] = 1;
    for (int i = 1; i <= maxN; i++) {
        p[i] = 1LL * p[i - 1] * K % MOD;
        invp[i] = fastPow(p[i], MOD - 2);
    }
}

void solve() {
    precalc();
    debug(invp[0]);
    string s;
    int q;
    cin >> s >> q;
    int n = s.size();
    vector<int> mp(n + 1, -1);
    unordered_map<int, vector<int>> ids[n + 1];
    int cur = -1;
    vector<int> h(n + 1);
    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] + 1LL * p[i] * (s[i] - 'a')) % MOD;
    }
    while (q--) {
        int k;
        string m;
        cin >> k >> m;
        int len = m.size();
        if (mp[len] == -1) {
            mp[len] = ++cur;
            for (int l = 0; l < n - len + 1; l++) {
                int r = l + len - 1;
                int hs = 1LL * (h[r + 1] - h[l]) * invp[l] % MOD;
                ids[mp[len]][hs].push_back(l);
            }
        }
        vector<int> hashm(len + 1);
        for (int i = 0; i < len; i++) {
            hashm[i + 1] = (hashm[i] + 1LL * p[i] * (m[i] - 'a')) % MOD;
        }
        vector<int> &id = ids[mp[len]][hashm[len]];
        int ans = INT_MAX;
        for (int l = 0; l < (int)id.size() - k + 1; l++) {
            int r = id[l + k - 1] + len;
            ans = min(ans, r - l);
        }
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}