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

#include <cassert>
#include <cstring>

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
	
template <const int N>
struct Automaton {
	static const int VN = 2 * N + 1;
	int root, last, n, len[VN], suf[VN], to[VN][26];

	inline int newV( int l, int _suf ) {
		assert(n < VN);
		memset(to[n], 0, sizeof(to[n]));
		len[n] = l, suf[n] = _suf;
		return n++;
	}
	void init() {
		n = 1, root = last = newV(0, 0);
	}
	void add( int ch ) {
		int r, q, p = last;
		last = newV(len[last] + 1, 0);
		while (!to[p][ch])
			to[p][ch] = last, p = suf[p];
		if (!p)
			suf[last] = 1;
		else if (len[q = to[p][ch]] == len[p] + 1)
			suf[last] = q;
		else {
			r = newV(len[p] + 1, suf[q]);
			suf[last] = suf[q] = r;
			memcpy(to[r], to[q], sizeof(to[r]));
			while (p && to[p][ch] == q)
				to[p][ch] = r, p = suf[p];
		}
	}
};