string s;

vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
	// s.data() + i
	// s.data() + j
	// bs k : hash [i,i+k) and [j,j+k)
});

// [i, i+len)
uint32_t getHash(int i, int len) {
	return (h[i+len] - 
		(uint64_t)h[i]*deg[len]) % mod;
}

// p, mod
int mod1 = 1e9 + 7 // простое
int mod2 = 1e9 + 9 // простое
p = random // [0,mod)

// 1e18 : double(8) sign*x*2^k
//			double 15-16
__int128 mod = (int64_t)1e18 + 3;

// mod = 2^{64}


// Суфф массив за nlogn

abc#

abc#
bc#a
c#ab
#abc

// Сортируем циклические сдвиги

// abcde

// abc k=3
// bcd
// cde
// dea
// eab

// Алгоритм

// База: k=1
// Отсортируем символы строки
// 	nlogn
// 	n+|Sigma|

// База: color[i] = s[i] // [0..n)
// Переход: k -> 2k : O(n)
0. p = {0, 1, 2, ..., n-1}
1. sort(p) : f(i) {color[i], color[i+k]}
2. 
	cc = 0
	for (int j = 0; j < n; j++)
		i1 = i, i = p[j]
		if f(i) != f(i1) // [i,i+2k) != [i1,i1+2k)
			cc++
		color2[i] = cc
	color = color2

// => O(nlogn)

// O(n log^2 n)
vector<int> SA(string s) {
	int n = s.size();
	vector<int> c(n), p(n), c2(n);
	forn(i, n) c[i] = s[i];
	iota(p.begin(), p.end(), 0);
	for (int k = 1; k < n; k *= 2) {
		#define f(i) make_pair(c[i],c[i+k])
		sort(p.begin(), p.end(), [&](i, j) {
			return f(i) < f(j);
		});
		int cc = 0, i = -1, i1;
		forn(j, n) {
			i1 = i, i = p[j];
			cc += (i1 != -1 && f(i) != f(i1));
			c[i] = cc
		}
		c = c2;
	}
	return p;
}

// O(n log n)
vector<int> SA(string s) {
	int n = s.size();
	vector<int> c(n), p(n), c2(n), p2(n);
	forn(i, n) c[i] = s[i];
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](i, j) {
		return s[i] < s[j];
	});
	for (int k = 1; k < n; k *= 2) {
		// p2 ??? O(n)
		vector<int> cnt(n), pos(n+1);
		for (int x : c) cnt[x]++;
		forn(i, n) pos[i+1] = pos[i] + cnt[i];
		forn(j, n) {
			int i = p[j]; // 2-я половина
			int i1 = (i - k + n) % n; // 1-я
			p2[pos[c[i1]]++] = i1;
		}	

		#define f(i) make_pair(c[i],c[i+k])
		int cc = 0, i = -1, i1;
		forn(j, n) {
			i1 = i, i = p2[j];
			cc += (i1 != -1 && f(i) != f(i1));
			c[i] = cc
		}
		c = c2, p = p2;
	}
	return p;
}





// алгоритм Касаи
// p1 = p^{-1}

i = p1[x+0]
j = p1[x+1]

Thm: lcp[j] >= lcp[i] - 1

lcp[i] = LCP(s + p[i], s + p[i+1])
lcp[j] = LCP(s + p[j], s + p[j+1])

vector<int> LCP(vector<int> p) { // p=SA
	int n = p.size();
	vector<int> lcp(n), p1(n);

	forn(i, n) // обратная перестановка
		p1[p[i]] = i;
	int k = 0;
	forn(i, n) { // s[i,n)
		// if (k == n) k = 0; // костыль
		k = max(k - 1, 0);
		// k = 0
		int x = p1[i];
		while (s[i + k] == s[p[x+1] + k])
			k++;
		lcp[x] = k;
	}
	return lcp;
}