#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl

ull BASE = 131;
// ull MOD = 140814840257324803;

ull powMod(ull x, ull y) {
  ull res = 1;
  for(; y > 0; y >>= 1, (x *= x)) {
    if(y & 1) (res *= x);
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  string S, T; cin >> S >> T;
  vector<int> match;
  ull target = 0;
  REP(i,T.size()) {
    target *= BASE;
    target += T[i];
    // target %= MOD;
  }
  // DEBUG(target);
  ull hash = 0;
  REP(i,S.size()) {
    if(i >= T.size()) {
      hash -= S[i - T.size()] * powMod(BASE, T.size() - 1);
      // if(hash < 0) hash += MOD;
    }
    hash *= BASE;
    hash += S[i];
    // DEBUG(hash);
    // hash %= MOD;
    if(hash == target) match.push_back(i - T.size() + 1);
  }
  for(int m : match) cout << m << endl;
}
### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl

ull BASE = 131;
// ull MOD = 140814840257324803;

ull powMod(ull x, ull y) {
  ull res = 1;
  for(; y > 0; y >>= 1, (x *= x)) {
    if(y & 1) (res *= x);
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  string S, T; cin >> S >> T;
  vector<int> match;
  ull target = 0;
  REP(i,T.size()) {
    target *= BASE;
    target += T[i];
    // target %= MOD;
  }
  // DEBUG(target);
  ull hash = 0;
  REP(i,S.size()) {
    if(i >= T.size()) {
      hash -= S[i - T.size()] * powMod(BASE, T.size() - 1);
      // if(hash < 0) hash += MOD;
    }
    hash *= BASE;
    hash += S[i];
    // DEBUG(hash);
    // hash %= MOD;
    if(hash == target) match.push_back(i - T.size() + 1);
  }
  for(int m : match) cout << m << endl;
}
```