//
// Created by ?????°?????? on 2016/06/21.
//

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

int main(){
    string t,p; cin >> t >> p;
    int nt = t.size();
    int np = p.size();
    if(nt < np) return 0;
    for (int i = 0; i < nt-np +1 ; ++i) {
        if(t[i]== p[0]){
            if(t.substr(i,np) == p) printf("%d\n",i);
        }
    }
    return 0;
}
### Prompt

Your challenge is to write 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
//
// Created by ?????°?????? on 2016/06/21.
//

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

int main(){
    string t,p; cin >> t >> p;
    int nt = t.size();
    int np = p.size();
    if(nt < np) return 0;
    for (int i = 0; i < nt-np +1 ; ++i) {
        if(t[i]== p[0]){
            if(t.substr(i,np) == p) printf("%d\n",i);
        }
    }
    return 0;
}
```