Find places where a string P is found within a text T. Print all indices of T where P found. The indices of T start with 0.

Constraints

* 1 ≤ length of T ≤ 1000000
* 1 ≤ length of P ≤ 10000
* The input consists of alphabetical characters and digits

Input

In the first line, a text T is given. In the second line, a string P is given.

Output

Print an index of T where P found in a line. Print the indices in ascending order.

Examples

Input

aabaaa
aa


Output

0
3
4


Input

xyzz
yz


Output

1


Input

abc
xyz


Output
#include<bits/stdc++.h>
#define MOD 1000000007

using namespace std;

long long fastpow(long long a, int b)
{
    if(b == 0) return 1;
    if(b % 2) return (a * fastpow(a, b-1))%MOD;
    long long c = fastpow(a, b/2);
    return (c * c)%MOD;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string tc, pt;
    cin>>tc;
    cin>>pt;
    
    long long n = tc.size();
    long long m = pt.size();
    long long m2 = m;
    long long h = fastpow(62,m2-1);

    long long patternheight = 0, tcheight = 0;
    for(long long i = 0; i < m2; i++){
        patternheight = (62 * patternheight + pt[i]) % MOD;
        tcheight = (62 * tcheight + tc[i]) % MOD;
    }

    for(long long i = 0; i <= n-m; i++){
        if(patternheight == tcheight){
           /* bool isMatched = true;
            for(long long j = 0; j < m && isMatched; j++)
            {
                if(p[j] != t[j+i]) isMatched = false;

            }
            if(isMatched) */cout<<i<<endl;

        }
        
        if(i < n-m) {
		tcheight = (62*(tcheight - (h*tc[i])) + tc[i+m2]) % MOD;
			}
		
        if(tcheight < 0){
		tcheight += MOD;
			}
    }
    return 0;
}
