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"
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using ull = unsigned long long;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
const double PI = acos(-1);
const double EPS = 1e-10;
const ull MOD = 1000000007;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
ull make_hash(string s,ll sz,ull b = 1e9+7){
  ull res = 0;
  ull tmp = 1;
  REP(i,sz){
    res += s[sz-i-1]*tmp;
    tmp *= b;
  }
  return res;
}
vector<ull> rolling_hash(string s,ll sz,ull b = 1e9+7){
  vector<ull> res;
  if((ll)s.size()<sz) return res;
  ull bn = 1; //bn:b^sz
  ull r = b, n = (ull)sz;
  for (; n > 0;n>>=1,r*=r) bn *= (n & 1? r:1);
  res.push_back(make_hash(s,sz));
  REP(i,(ll)s.size()-sz){
    ull tmp = b * res.back();
    tmp -= bn*s[i];
    tmp += s[sz+i];
    res.push_back(tmp);
  }
  return res;
}

int main(){
  string t,p;
  cin >> t >> p;
  ull hash_p = make_hash(p,(ll)p.size());
  auto hash = rolling_hash(t,p.size());
  REP(i,(ll)(hash.size())){
    if(hash_p == hash[i]) cout << i << endl;
  }
}


