#include <iostream>
#include <string>
#include <vector>

class KMPSearch {
private:
    std::string T;

public:
    std::vector<int> border;
    // S[0,border[i]-1]はS[0,i-1]の接頭辞かつ接尾辞
    // かつS[border[i]] != S[i]を満たす

    KMPSearch(std::string T) : T(T), border(T.length() + 1, -1) {
        int j = -1;  // border[i+1]を指す
        for (int i = 0; i < T.length(); ++i) {
            while (j >= 0 && T[i] != T[j]) j = border[j];
            ++j;
            if (i + 1 < T.length() && T[i + 1] == T[j]) {
                border[i + 1] = border[j];
            } else {
                border[i + 1] = j;
            }
        }
    }

    std::vector<int> search(std::string S) {
        std::vector<int> ret;
        int j = 0;
        for (int i = 0; i + T.length() - 1 < S.length();) {
            for (; j < T.length(); ++j) {
                if (S[i + j] != T[j]) break;
            }
            if (j == T.length()) ret.push_back(i);
            // T[0,j-1]は一致している
            // よってj-border[j]ずらせる
            i += j - border[j];
            // このとき既にT[0,border[j]-1]は一致している
            j = std::max(0, border[j]);
        }
        return ret;
    }
};

int main() {
    std::string S, T;
    std::cin >> S >> T;
    KMPSearch kmps(T);
    auto ans = kmps.search(S);
    for (auto i : ans) std::cout << i << std::endl;
    return 0;
}


### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include <iostream>
#include <string>
#include <vector>

class KMPSearch {
private:
    std::string T;

public:
    std::vector<int> border;
    // S[0,border[i]-1]はS[0,i-1]の接頭辞かつ接尾辞
    // かつS[border[i]] != S[i]を満たす

    KMPSearch(std::string T) : T(T), border(T.length() + 1, -1) {
        int j = -1;  // border[i+1]を指す
        for (int i = 0; i < T.length(); ++i) {
            while (j >= 0 && T[i] != T[j]) j = border[j];
            ++j;
            if (i + 1 < T.length() && T[i + 1] == T[j]) {
                border[i + 1] = border[j];
            } else {
                border[i + 1] = j;
            }
        }
    }

    std::vector<int> search(std::string S) {
        std::vector<int> ret;
        int j = 0;
        for (int i = 0; i + T.length() - 1 < S.length();) {
            for (; j < T.length(); ++j) {
                if (S[i + j] != T[j]) break;
            }
            if (j == T.length()) ret.push_back(i);
            // T[0,j-1]は一致している
            // よってj-border[j]ずらせる
            i += j - border[j];
            // このとき既にT[0,border[j]-1]は一致している
            j = std::max(0, border[j]);
        }
        return ret;
    }
};

int main() {
    std::string S, T;
    std::cin >> S >> T;
    KMPSearch kmps(T);
    auto ans = kmps.search(S);
    for (auto i : ans) std::cout << i << std::endl;
    return 0;
}


```