Opencup K

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

#define sz(x) ((int)(x.size()))
#define pb push_back

typedef long long ll;

const int N = 100000;
const int M = 1000000;

const ll P1 = 31;
const ll P2 = 29;

const ll MOD1 =  999999997;
const ll MOD2 = 1000000007;

ll p_pow1[M + 1];
ll p_pow2[M + 1];

ll h1[M + 1];
ll h2[M + 1];

char s[M + 1];

unordered_set<long long> used[N + 1];

inline int lcp(ll h1[], ll h2[], int n) {
  int l = 0, r = n + 1;
  while (r - l > 1) {
    int m = (l + r) / 2;
    ll cur_h1 = (h1[m] - h1[0] * p_pow1[m]) % MOD1;
    ll cur_h2 = (h2[m] - h2[0] * p_pow2[m]) % MOD2;
    if (cur_h1 < 0) cur_h1 += MOD1;
    if (cur_h2 < 0) cur_h2 += MOD2;
    if (used[m].find(cur_h1 ^ (cur_h2 << 32)) != used[m].end()) {
      l = m;
    } else {
      r = m;
    }
  }
  return l;
}

int main() {
  int n;
  scanf("%d\n", &n);
  for (int i = 0; i < n; ++i) {
    gets(s);
    int len = strlen(s);
    ll cur_h1 = 0;
    ll cur_h2 = 0;
    for (int j = 0; j < len; ++j) {
      cur_h1 *= P1;
      cur_h2 *= P2;
      cur_h1 += s[j] - 'a' + 1;
      cur_h2 += s[j] - 'a' + 1;
      cur_h1 %= MOD1;
      cur_h2 %= MOD2;
      used[j + 1].insert(cur_h1 ^ (cur_h2 << 32));
    }
  }

  p_pow1[0] = 1;
  p_pow2[0] = 1;
  for (int i = 0; i < M; ++i) {
    p_pow1[i + 1] = p_pow1[i] * P1 % MOD1;
    p_pow2[i + 1] = p_pow2[i] * P2 % MOD2;

  }
  int m;
  scanf("%d\n", &m);
  for (int i = 0; i < m; ++i) {
    gets(s);
    int len = strlen(s);
    h1[0] = 0;
    h2[0] = 0;
    for (int j = 0; j < len; ++j) {
      h1[j + 1] = (h1[j] * P1 + s[j] - 'a' + 1) % MOD1;
      h2[j + 1] = (h2[j] * P2 + s[j] - 'a' + 1) % MOD2;
    }
    for (int j = 0; j < len; ++j) {
      printf("%d ", lcp(h1 + j, h2 + j, min(N, len - j)));
    }
    printf("\n");
  }

  return 0;
}