typedef unsigned long long ull;

const int N = 1e5;
const int P = 239017;

char s[N + 1];
ull h[N + 1], deg[N + 1];

void init() {
  int n = strlen(s);
  deg[0] = 1, h[0] = 0;
  forn(i, n) {
    h[i + 1] = h[i] * P + s[i];
    deg[i + 1] = deg[i] * P;
  }
}

ull getHash( int i, int len ) {
  return h[i + len] - h[i] * deg[len];
}