#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

// Function to count substrings containing at least one '*'
long long countMaliciousSubstrings(const string& password) {
    long long total = 0;
    int n = password.size();
    int lastClean = -1;

    for (int i = 0; i < n; ++i) {
        if (password[i] == '*') {
            int len = i - lastClean - 1;
            total += (1LL * len * (len + 1)) / 2;
            lastClean = i;
        }
    }

    int len = n - lastClean - 1;
    total += (1LL * len * (len + 1)) / 2;

    long long totalSubstrings = (1LL * n * (n + 1)) / 2;
    return totalSubstrings - total;
}

// Main function to find minimum time after which password becomes irrecoverable
int minTimeToIrrecoverable(string password, vector<int>& attackOrder, long long m) {
    int n = password.size();
    int left = 1, right = n, ans = n + 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        string temp = password;

        // Simulate attack for 'mid' seconds
        for (int i = 0; i < mid; ++i) {
            temp[attackOrder[i]] = '*';
        }

        long long malicious = countMaliciousSubstrings(temp);

        if (malicious >= m) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return (ans == n + 1) ? -1 : ans;
}

// Example usage
int main() {
    string password;
    int n;
    long long m;

    cout << "Enter password: ";
    cin >> password;

    cout << "Enter number of attack indices: ";
    cin >> n;

    vector<int> attackOrder(n);
    cout << "Enter attack order (0-indexed): ";
    for (int i = 0; i < n; ++i) {
        cin >> attackOrder[i];
    }

    cout << "Enter m (number of substrings with '*'): ";
    cin >> m;

    int result = minTimeToIrrecoverable(password, attackOrder, m);
    cout << "Minimum time to become irrecoverable: " << result << endl;

    return 0;
}