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 <iostream>
#include <vector>
#include <string>
using namespace std;

// ----- MP algorithm -----

template <typename Type = string>
class MP
{
  int N;
  Type S;
  vector<int> A;

public:
  MP() {}
  MP(Type const &S) : N(S.size()), S{S}, A(N + 1, -1)
  {
    int j{-1};
    for (auto i{0}; i < N; i++)
    {
      while (j != -1 && S[j] != S[i])
      {
        j = A[j];
      }
      ++j;
      A[i + 1] = j;
    }
  }

  int operator[](int i) const { return A[i]; }

  int period(int i) const { return i - A[i]; }

  vector<int> place(Type const &T) const
  {
    vector<int> res;
    int j{0};
    for (auto i{size_t{0}}; i < T.size(); i++)
    {
      while (j != -1 && S[j] != T[i])
      {
        j = A[j];
      }
      ++j;
      if (j == N)
      {
        res.push_back(i - j + 1);
        j = A[j];
      }
    }
    return res;
  }

  vector<bool> table(Type const &T) const
  {
    vector<bool> res(T.size(), false);
    for (auto e : place(T))
    {
      res[e] = true;
    }
    return res;
  }
};

int main()
{
  string t, p;
  cin >> t >> p;
  MP<string> mp{p};
  for (auto e : mp.place(t))
  {
    cout << e << endl;
  }
}

