/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include <cstring>
#include <cassert>

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define zero(a) memset(a, 0, sizeof(a))

template <const int maxV, const int E>
struct AhoCorasic {
  struct Vertex {
    int next[E], p, dep, ch, suf, end;
  };

  int vn;
  Vertex a[maxV];
  int qst, qen, q[maxV];

  int newV( int P, int D, int K ) {
    assert(vn < maxV);
    Vertex &v = a[vn];
    v.dep = D, v.ch = K, v.p = P, v.end = 0;
    zero(v.next);
    return vn++;
  }

  AhoCorasic() {
    vn = 0, newV(-1, 0, -1);
  }

  void add( const char *s ) {
    int v = 0;
    while (*s) {
      int ch = *s++ - 'a', &x = a[v].next[ch];
      if (!x)
        x = newV(v, a[v].dep + 1, ch);
      v = x;
    }
    a[v].end = 1;
  }

  void build() {
    qst = qen = 0;
    q[qen++] = 0;
    while (qst < qen) {
      int v = q[qst++];
      Vertex &V = a[v];
      V.suf = (V.dep <= 1 ? 0 : a[a[V.p].suf].next[V.ch]);
      forn(i, 26)
        if (V.next[i])
          q[qen++] = V.next[i];
        else 
          V.next[i] = a[V.suf].next[i];
      V.end |= a[V.suf].end;
    }
  }
};

AhoCorasic<(int)1e5, 26> m;
