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>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;
#define ull unsigned long long

vector<ll> rolling_hash(string A, string S) {
  ll al = A.size(), sl = S.size();
  vector<ll> res = {};
  if (al > sl) {
    return res;
  }
  ull cardinal = 1000000007;
  ull ah = 0, sh = 0;
  ull cardinal_pow = 1;
  for (ll i = 0; i < al; ++i) {
    ah = ah * cardinal + (A[i] - 'A');
    sh = sh * cardinal + (S[i] - 'A');
    cardinal_pow *= cardinal;
  }
  if (ah == sh) {
    res.push_back(0);
  }
  for (ll i = 0; i < sl - al; ++i) {
    sh = sh * cardinal - (S[i] - 'A') * cardinal_pow + (S[i + al] - 'A');
    if (sh == ah) {
      res.push_back(i + 1);
    }
  }
  return res;
}

int main() {
  string A, S;
  cin >> S >> A;
  vector<ll> ans = rolling_hash(A, S);
  for (ll i = 0; i < ans.size(); ++i) {
    cout << ans.at(i) << "\n";
  }
}

