    /**
     * 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;