RABIN-KARP

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 1;
const int mod = 1e9 + 7;
const ll p = 31;
ll power[N];
ll mul(ll x , ll y)
{
    return ((x%mod)*(y%mod))%mod;
}
ll add(ll x , ll y)
{
    return (x%mod+y%mod)%mod;
}
ll sub(ll x , ll y)
{
    return ((x % mod - y % mod + mod))%mod;
}
void pre()
{
    power[0] = 1;
    for(int i = 1 ; i <= N ; i++ )
    {
        power[i] = mul(p,power[i-1]);
    }
}

void hash_func(string const &s , string const &p)
{



    ll hp = 0 ;
    ll n = s.size();
    ll pl = p.size();
    for(int i = 0 ; i < p.size() ; i++ )
    {
        hp = add(hp,mul(p[i] - 'a' + 1 , power[i]));
    }

        vector < ll > hs(n+1,0),ans;
    for(int i = 0 ; i < s.size() ; i++ )
    {

        hs[i+1] = add(hs[i],mul(s[i] - 'a' + 1 , power[i]));

    }

    for(int i = 0 ; i  <= n - pl  ; i++)
    {
        ll curr = sub(hs[i+pl] , hs[i]);
        if(curr == mul(hp,power[i]))
            ans.pb(i);
    }

    if(ans.empty())
        cout << "\n";
    else
    {
        //cout << ans.size() << "\n";
        for(auto it : ans)
        cout << it << "\n";
        cout << "\n";
    }
    cout << "\n";


}

int main()
{
    fast;
    pre();
    ll t;

    string s , p;
    while(cin >> t)
    {
        cin >> p >> s;
        hash_func(s,p);
    }













    return 0;

}