#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// ------ Suffix Array ------ //
class SuffixArray {
	void CreateBeginBucket(vector<int>&v, vector<int>&bucket) {
		fill(bucket.begin(), bucket.end(), 0);
		for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
		int sum = 0;
		for (int i = 0; i<bucket.size(); i++) { bucket[i] += sum; swap(sum, bucket[i]); }
	}
	void CreateEndBucket(vector<int>&v, vector<int>&bucket) {
		fill(bucket.begin(), bucket.end(), 0);
		for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
		for (int i = 1; i<bucket.size(); i++)bucket[i] += bucket[i - 1];
	}
	void InducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
		CreateBeginBucket(v, bucket);
		for (int i = 0; i<v.size(); i++)if (SA[i]>0 && isL[SA[i] - 1])SA[bucket[v[SA[i] - 1]]++] = SA[i] - 1;
	}
	void InvertInducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
		CreateEndBucket(v, bucket);
		for (int i = v.size() - 1; i >= 0; i--)if (SA[i]>0 && !isL[SA[i] - 1])SA[--bucket[v[SA[i] - 1]]] = SA[i] - 1;
	}
	vector<int>SA_IS(vector<int>v, int mv) {
		if (v.size() == 1)return vector<int>(1, 0);
		vector<int>isL(v.size());
		vector<int>bucket(mv + 1);
		vector<int>SA(v.size(), -1);
		auto isLMS = [&](int x)->bool {return x>0 && isL[x - 1] && !isL[x]; };
		isL[v.size() - 1] = 0;
		for (int i = v.size() - 2; i >= 0; i--)isL[i] = v[i]>v[i + 1] || (v[i] == v[i + 1] && isL[i + 1]);
		CreateEndBucket(v, bucket);
		for (int i = 0; i<v.size(); i++)if (isLMS(i))SA[--bucket[v[i]]] = i;
		InducedSort(v, SA, mv, bucket, isL);
		InvertInducedSort(v, SA, mv, bucket, isL);
		int cur = 0;
		vector<int>ord(v.size());
		for (int i = 0; i<v.size(); i++)if (isLMS(i))ord[i] = cur++;
		vector<int>nxv(cur);
		cur = -1;
		int prev = -1;
		for (int i = 0; i<v.size(); i++) {
			if (!isLMS(SA[i]))continue;
			bool diff = false;
			for (int d = 0; d<v.size(); d++) {
				if (prev == -1 || v[SA[i] + d] != v[prev + d] || isL[SA[i] + d] != isL[prev + d]) {
					diff = true;
					break;
				}
				else if (d>0 && isLMS(SA[i] + d))break;
			}
			if (diff) { cur++; prev = SA[i]; }
			nxv[ord[SA[i]]] = cur;
		}
		vector<int>reord(nxv.size());
		for (int i = 0; i<v.size(); i++)if (isLMS(i))reord[ord[i]] = i;
		vector<int>nxSA = SA_IS(nxv, cur);
		CreateEndBucket(v, bucket);
		for (int i = 0; i<SA.size(); i++)SA[i] = -1;
		for (int i = nxSA.size() - 1; i >= 0; i--)SA[--bucket[v[reord[nxSA[i]]]]] = reord[nxSA[i]];
		InducedSort(v, SA, mv, bucket, isL);
		InvertInducedSort(v, SA, mv, bucket, isL);
		return SA;
	}
	vector<int>SA_IS(string s) {
		vector<int>v(s.size() + 1);
		for (int i = 0; i<s.size(); i++)v[i] = s[i] + 1;
		return SA_IS(v, *max_element(v.begin(), v.end()));
	}
	vector<int>construct_lcp(string &s, vector<int>&sa) {
		vector<int> lcp, rank(s.size() + 1);
		int n = s.size();
		for (int i = 0; i <= n; i++)rank[sa[i]] = i;
		int h = 0;
		lcp[0] = 0;
		for (int i = 0; i<n; i++) {
			int j = sa[rank[i] - 1];
			if (h>0) h--;
			for (; j + h<n&&i + h<n; h++) {
				if (s[j + h] != s[i + h])break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
public:
	string s;
	vector<int> sa, lcp;
	void init(string &T) {
		s = T;
		sa = SA_IS(s);
	}
	SuffixArray(string &t) { init(t); }
	SuffixArray() {}
	bool contain(string &t) {
		int a = 0, b = s.size();
		while (b - a>1) {
			int c = (a + b) / 2;
			if (s.compare(sa[c], t.size(), t) < 0)a = c;
			else b = c;
		}
		return s.compare(sa[b], t.size(), t) == 0;
	}
};