#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long power(int a, int b) {
const int m = 1e9 + 9;
const int p = 7;
long long result = a;
for (int i = 0; i < b; i++) {
result *= p;
result %= m;
}
return result;
}
long long compute_hash(string const& s) {
const int p = 7;
const int m = 1e9 + 9;
long long hash_value = 0;
long long p_pow = 1;
for (char c : s) {
hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
p_pow = (p_pow * p) % m;
}
return hash_value;
}
long long rolling_hash(string const& previous_substring, long long previous_hash, char next_char) {
const int p = 7;
const int m = 1e9 + 9;
long long hash_value = ((previous_hash - (previous_substring[0] - 'a' + 1)) / p + power((next_char - 'a' + 1), previous_substring.length() - 1)) % m;
return hash_value;
}
int main()
{
string needle, haystack;
int needle_length, haystack_length;
long long needle_hash, substring_hash;
bool found;
while (cin >> needle_length >> needle >> haystack) {
haystack_length = haystack.length();
needle_hash = compute_hash(needle);
vector<pair<long long, int>> hashes;
substring_hash = compute_hash(haystack.substr(0, needle_length));
hashes.push_back({ substring_hash , 0 });
for (int i = 1; i <= haystack_length - needle_length; i++) {
substring_hash = rolling_hash(haystack.substr(i - 1, needle_length), substring_hash, haystack[i + needle_length - 1]);
hashes.push_back({ substring_hash , i});
}
found = false;
for (int i = 0; i < hashes.size(); i++) {
if (hashes[i].first == needle_hash) {
found = true;
cout << hashes[i].second << '\n';
}
}
if (!found) cout << '\n';
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBwb3dlcihpbnQgYSwgaW50IGIpIHsKICAgIGNvbnN0IGludCBtID0gMWU5ICsgOTsKICAgIGNvbnN0IGludCBwID0gNzsgCgogICAgbG9uZyBsb25nIHJlc3VsdCA9IGE7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGI7IGkrKykgewogICAgICAgIHJlc3VsdCAqPSBwOwogICAgICAgIHJlc3VsdCAlPSBtOwogICAgfQoKICAgIHJldHVybiByZXN1bHQ7Cn0KCmxvbmcgbG9uZyBjb21wdXRlX2hhc2goc3RyaW5nIGNvbnN0JiBzKSB7CiAgICBjb25zdCBpbnQgcCA9IDc7IAogICAgY29uc3QgaW50IG0gPSAxZTkgKyA5OwogICAgbG9uZyBsb25nIGhhc2hfdmFsdWUgPSAwOwogICAgbG9uZyBsb25nIHBfcG93ID0gMTsKICAgIGZvciAoY2hhciBjIDogcykgewogICAgICAgIGhhc2hfdmFsdWUgPSAoaGFzaF92YWx1ZSArIChjIC0gJ2EnICsgMSkgKiBwX3BvdykgJSBtOwogICAgICAgIHBfcG93ID0gKHBfcG93ICogcCkgJSBtOwogICAgfQoKICAgIHJldHVybiBoYXNoX3ZhbHVlOwp9Cgpsb25nIGxvbmcgcm9sbGluZ19oYXNoKHN0cmluZyBjb25zdCYgcHJldmlvdXNfc3Vic3RyaW5nLCBsb25nIGxvbmcgcHJldmlvdXNfaGFzaCwgY2hhciBuZXh0X2NoYXIpIHsKICAgIGNvbnN0IGludCBwID0gNzsgCiAgICBjb25zdCBpbnQgbSA9IDFlOSArIDk7CgogICAgbG9uZyBsb25nIGhhc2hfdmFsdWUgPSAoKHByZXZpb3VzX2hhc2ggLSAocHJldmlvdXNfc3Vic3RyaW5nWzBdIC0gJ2EnICsgMSkpIC8gcCArIHBvd2VyKChuZXh0X2NoYXIgLSAnYScgKyAxKSwgcHJldmlvdXNfc3Vic3RyaW5nLmxlbmd0aCgpIC0gMSkpICUgbTsKCiAgICByZXR1cm4gaGFzaF92YWx1ZTsKfQoKaW50IG1haW4oKQp7CgogICAgc3RyaW5nIG5lZWRsZSwgaGF5c3RhY2s7CiAgICBpbnQgbmVlZGxlX2xlbmd0aCwgaGF5c3RhY2tfbGVuZ3RoOwogICAgbG9uZyBsb25nIG5lZWRsZV9oYXNoLCBzdWJzdHJpbmdfaGFzaDsKICAgIGJvb2wgZm91bmQ7CgogICAgd2hpbGUgKGNpbiA+PiBuZWVkbGVfbGVuZ3RoID4+IG5lZWRsZSA+PiBoYXlzdGFjaykgewogICAgICAgIGhheXN0YWNrX2xlbmd0aCA9IGhheXN0YWNrLmxlbmd0aCgpOwogICAgICAgIG5lZWRsZV9oYXNoID0gY29tcHV0ZV9oYXNoKG5lZWRsZSk7CgogICAgICAgIHZlY3RvcjxwYWlyPGxvbmcgbG9uZywgaW50Pj4gaGFzaGVzOwogICAgICAgIHN1YnN0cmluZ19oYXNoID0gY29tcHV0ZV9oYXNoKGhheXN0YWNrLnN1YnN0cigwLCBuZWVkbGVfbGVuZ3RoKSk7CiAgICAgICAgaGFzaGVzLnB1c2hfYmFjayh7IHN1YnN0cmluZ19oYXNoICwgMCB9KTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gaGF5c3RhY2tfbGVuZ3RoIC0gbmVlZGxlX2xlbmd0aDsgaSsrKSB7CiAgICAgICAgICAgIHN1YnN0cmluZ19oYXNoID0gcm9sbGluZ19oYXNoKGhheXN0YWNrLnN1YnN0cihpIC0gMSwgbmVlZGxlX2xlbmd0aCksIHN1YnN0cmluZ19oYXNoLCBoYXlzdGFja1tpICsgbmVlZGxlX2xlbmd0aCAtIDFdKTsKICAgICAgICAgICAgaGFzaGVzLnB1c2hfYmFjayh7IHN1YnN0cmluZ19oYXNoICwgaX0pOwogICAgICAgIH0KICAgICAgICBmb3VuZCA9IGZhbHNlOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgaGFzaGVzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgIGlmIChoYXNoZXNbaV0uZmlyc3QgPT0gbmVlZGxlX2hhc2gpIHsKICAgICAgICAgICAgICAgIGZvdW5kID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGNvdXQgPDwgaGFzaGVzW2ldLnNlY29uZCA8PCAnXG4nOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmICghZm91bmQpIGNvdXQgPDwgJ1xuJzsKICAgIH0KCgogICAgcmV0dXJuIDA7Cn0KCg==