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 <iostream>
#include <string>

std::string GetSub(const std::string& P)
{
    for(std::size_t i = 1; i < P.size(); ++i){
        int n = P.size() - i;
        if(P.substr(i) == P.substr(0, n)){
            return P.substr(n);
        }
    }
    return P;
}
int main()
{
    std::string T, P;

    std::cin >> T >> P;
    const int Skip = P.size();
    const std::string Sub = GetSub(P);
    // std::cerr << "Skip:" << Skip << ", Sub:" << Sub << std::endl;
    int Pos = T.find(P, 0);
    while(Pos != std::string::npos){
        std::cout << Pos << std::endl;
        if(T.substr(Pos + Skip, Sub.size()) == Sub){
            Pos += Sub.size();
        }else{
            Pos = T.find(P, Pos + Skip);
        }
    }
    return 0;
}