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

#include <cassert>
#include <map>

using namespace std;

#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];
	map<int, int> to[VN];

	inline int newV( int l, int _suf ) {
		assert(n < VN);
		len[n] = l, suf[n] = _suf, to[n].clear();
		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 (p && !to[p].count(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;
			to[r] = to[q];
			while (p && to[p][ch] == q)
				to[p][ch] = r, p = suf[p];
		}
	}
};