class Fun {
	vi p,c,lcp,logi;
	vector<vi> seg;
	string s1,s2,s;
	ll len1,len2;

	Fun(string p, string q) {
		s1 = p;
		s2 = q;
		len1 = p.length();
		len2 = q.length();
		suffix_array(s1+'$'+s2);
		preprocess();
	}

	ll findMatch(ll i,ll j) {
		return findLcp(i,len1 + 1 + j);
	}

	// void showMe(string s) {
	// 	ll n = s.length();
	// 	rep(i,0,n) {
	// 		cerr << s.substr(p[i], n - p[i]) << " " << c[p[i]] << " " << lcp[i] << endl;
	// 	}
	// 	cerr << endl;
	// }

	void count_sort() {
		ll n = p.size();
		vi count(n,0);
		trav(i,c) {
			count[i]++;
		}
		rep(i, 1, n) {
			count[i] += count[i - 1];
		}
		repr(i, 0, n - 1) {
			count[i + 1] = count[i];
		}
		count[0] = 0;
		vi p_new(n);
		trav(i,p) {
			p_new[count[c[i]]] = i;
			count[c[i]]++;
		}
		p = p_new;
	}


	void suffix_array(string s) {
		s += (char)0;
		ll n = s.length();
		p.resize(n);
		c.resize(n);
		lcp.resize(n);


		vi freq(256, 0);
		rep(i, 0, n) {
			freq[s[i]]++;
		}
		rep(i,1,256) {
			freq[i] += freq[i - 1];
		}
		repr(i,0,255) {
			freq[i + 1] = freq[i];
		}
		freq[0] = 0;


		p[0] = n - 1;
		rep(i, 0, n - 1) {
			p[freq[s[i]]] = i;
			freq[s[i]]++;
		}

		c[p[0]] = 0;
		rep(i, 1, n) {
			if(s[p[i]] == s[p[i - 1]]) {
				c[p[i]] = c[p[i - 1]];
			} else {
				c[p[i]] = c[p[i - 1]] + 1;
			}
		}

		// showMe(s);

		vi c_new(n);
		ll k = 0;
		while((1 << k) < n) {
			rep(i, 0, n) {
				p[i] = (p[i] - (1 << k) + n) % n;
			}
			// DEBUG;
			count_sort();
			c_new[p[0]] = 0;
			pii pre,now;
			pre = {c[p[0]], c[(p[0] + (1 << k)) % n]};
			rep(i,1,n) {
				now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
				if(now == pre) {
					c_new[p[i]] = c_new[p[i - 1]];
				} else {
					c_new[p[i]] = c_new[p[i - 1]] + 1;
				}
				pre = now;
			}
			k++;
			c = c_new;
			// showMe(s);
		}

		k = 0;
		rep(i, 0, n - 1) {
			ll pi = c[i];
			ll j = p[pi - 1];
			while(s[i + k] == s[j + k]) {
				k++;
			}
			lcp[pi - 1] = k;
			k = max(k - 1, 0);
		}
		// showMe(s);
	}

	ll findLcp(ll l,ll r) {
		l = c[l];
		r = c[r];
		if(l > r) {
			swap(l,r);
		}
		r--;
		ll lg = logi[r - l + 1];
		return min(seg[l][lg], seg[r - (1 << lg) + 1][lg]);
	}


	void preprocess() {
		ll n = sz(p) - 1;

		logi.resize(n + 1);

		logi[1] = 0;

		rep(i, 2, n + 1) {
			logi[i] = logi[i / 2] + 1;
		}

		ll lg = logi[n];

		seg = vector<vi> (n, vi(lg + 1));

		rep(i, 0, n) {
			seg[i][0] = lcp[i];
		}

		for(ll j = 1; (1 << j) < n; j++) {
			rep(i, 0, n) {
				seg[i][j] = min(seg[i][j - 1], seg[min(n - 1, i + (1 << (j - 1)))][j - 1]);
			}
		}
	}
}