#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>

class SuffixNode {
public:
    SuffixNode(int index, int x, int y) {
        this->index = index;
        rank[0] = x;
        rank[1] = y;
    }

    int index;
    int rank[2];
};

int cmp(SuffixNode a, SuffixNode b) {
    return (a.rank[0] == b.rank[0]) ? (a.rank[1] < b.rank[1]) : (a.rank[0] < b.rank[0]);
}

std::vector<int> buildArray(std::string text) {
    std::vector<SuffixNode> sufArr;
    std::vector<int> indices;
    std::vector<int> result;
    for (int i = 0; i < text.size(); i++) {
        indices.push_back(0);
        sufArr.push_back(SuffixNode(i, text[i] - 'a', ((i + 1) < text.size()) ? (text[i + 1] - 'a') : -1));
    }
    std::sort(sufArr.begin(), sufArr.end(), cmp);

    for (int k = 4; k < text.size() * 2; k *= 2) {
        int curRank = 0;
        int prevRank = sufArr[0].rank[0];
        sufArr[0].rank[0] = curRank;
        indices[sufArr[0].index] = 0;
        for (int i = 1; i < text.size(); i++) {
            if (sufArr[i].rank[0] == prevRank && sufArr[i].rank[1] == sufArr[i - 1].rank[1]) {
                prevRank = sufArr[i].rank[0];
                sufArr[i].rank[0] = curRank;
            } else {
                prevRank = sufArr[i].rank[0];
                curRank++;
                sufArr[i].rank[0] = curRank;
            }
            indices[sufArr[i].index] = i;
        }
        for (int i = 0; i < text.size(); i++) {
            sufArr[i].rank[1] = (sufArr[i].index + k / 2 < text.size()) ? sufArr[indices[sufArr[i].index + k / 2]].rank[0]: -1;
        }
        std::sort(sufArr.begin(), sufArr.end(), cmp);
    }

    for (auto suf : sufArr)
        result.push_back(suf.index);
    return result;
}


std::vector<std::vector<int>> patternSearch(const std::vector<std::string> &patterns, const std::vector<int> &array, std::string text) {
    std::vector<std::vector<int>> cheshskieprostitutki;
    for (int j = 0; j < patterns.size(); j++) {
        std::vector<int> ocurrences;
        bool flag = false;
        for (int i = 0; i < array.size(); i++) {
            if (patterns[j].size() <= text.size() - array[i] && patterns[j] == text.substr(array[i], patterns[j].size())) {
                flag = true;
                ocurrences.push_back(array[i]);
            } else if (flag)
                break;
        }
        std::sort(ocurrences.begin(), ocurrences.end());
        cheshskieprostitutki.push_back(ocurrences);
    }
    return cheshskieprostitutki;//<3333333333333333333333333333333333333333333
}

std::vector<std::string> readFile()
{
    std::ifstream file("input.txt");
    std::vector<std::string> result;
    while (file.good()) {
        std::string crutch;
        std::getline(file, crutch);
        if (crutch != "")
            result.push_back(crutch);
    }
    file.close();
    return result;
}

void printSuffix(std::vector<std::vector<int>> results)
{
    for (int i = 0; i < results.size(); i++) {
        if(results[i].empty()) {
            continue;
        }
        std::cout << i + 1 << ": ";
        for (int j = 0; j < results[i].size(); j++) {
            if (j != 0)
                std::cout << ", ";
            std::cout << results[i][j] + 1;
        }
        if (i != results.size() - 1)
            std::cout << '\n';
    }
    return;
}

int main() {
    std::vector<std::string> lines = readFile();
    std::string text = lines[0];
    lines.erase(lines.begin());

    std::vector<int> sufArr = buildArray(text);
    std::vector<std::vector<int>> ocurrences = patternSearch(lines, sufArr, text);

    printSuffix(ocurrences);
}