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>

using namespace std;

char text[1000010],p[10010];

#define next Next
int next[10010];
int len;

void getNext()
{
    int i,j;
    j=next[0]=-1;
    i=0;
    while(p[i])
    {
        while(j!=-1&&p[i]!=p[j]) j=next[j];
        if(p[++i]==p[++j]) next[i]=next[j];
        else next[i]=j;
    }
    len=i;
}

int KMP()
{
    int i,j;
    int ans=0;

    getNext();
    i=j=0;
    while(text[i])
    {
        while(-1!=j&&text[i]!=p[j]) j=next[j];
        i++,j++;
        if(j>=len)
        {
            ans++;
            j=next[j];
            printf("%d\n",i-len);
        }
    }
    return ans;
}

int main()
{
    cin>>text>>p;

    KMP();

    return 0;
}

