前置知识：简要了解 CRT 和高斯消元

题意简述：给定一些系数，求 $n$ 元线性同余方程组 $A_i+\sum^{M}_{j=1}a_{i,j}x_j\equiv B_i(\mod 365)$ 的解。

注意到 $365=5\times73$，而且他们都是质数，这引导着我们思考先分别求出模 $5,73$ 意义下的解，然后使用 CRT 来合并答案。
对固定的质数求解 $n$ 元线性同余方程组的具体步骤，首先我们考虑把所有数字都放在模意义下，我们发现这个问题就变成了求解线性方程组的问题，用高斯消元法求解即可。
换言之：求解 $n$ 元线性同余方程组，就是模意义下的高斯消元。
下面说一些实现细节。

• 1.我们读取日期的时候需要注意每个月的日子各不相同，开个数组存一下，然后我个人比较喜欢封装的写法，因此有了下面的代码：

int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int date() {
    int d, m;
    scanf("%d %d", &d, &m);
    for (int i = 0; i < m - 1; ++i)
        d += days[i];
    return d - 1;
}

• 2.因为模数固定且质因子较少，我们直接手算式子就行。代码如下：

    for (int i = 0; i < M; ++i) {
        printf("%d\n", (146 * Sol5[i] + 220 * Sol73[i] + 364) % 365 + 1);
    }

• 3.做除法的时候别忘了，其实是要乘以逆元的。

差不多就这些了，下面贴个代码：

#include <bits/stdc++.h>
using namespace std;
const int maxN = 205, maxM = 205;

int N, M;
int mts[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int Init[maxN][maxM + 1], tmp[maxN][maxM + 1];
int date() {
    int d, m;
    scanf("%d %d", &d, &m);
    for (int i = 0; i < m - 1; ++i)
        d += mts[i];
    return d - 1;
}
int Sol5[maxM], Sol73[maxM], inv[100];
void get_inv(int p) {
    inv[0] = 0;
    for (int i = 1; i < p; ++i)
        for (int j = 1; j < p; ++j)
            if ((i * j) % p == 1)
                inv[i] = j;
}
void Gauss(int p, int* Sol) {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= M; ++j)
            tmp[i][j] = Init[i][j] % p;
    get_inv(p);
    int valid = 0;
    for (int s = 0; s < M; ++s) {
        int ff = -1;
        for (int i = valid; ff == -1 && i < N; ++i)
            if (tmp[i][s] != 0)
                ff = i;
        if (ff == -1)
            continue;
        if (valid != ff)
            for (int i = 0; i <= M; ++i)
                swap(tmp[valid][i], tmp[ff][i]);
        int rev = inv[tmp[valid][s]];
        for (int i = 0; i <= M; ++i)
            tmp[valid][i] = (tmp[valid][i] * rev) % p;
        for (int i = 0; i < N; ++i)
            if (i != valid) {
                int cf = tmp[i][s];
                for (int j = 0; j <= M; ++j) {
                    tmp[i][j] -= cf * tmp[valid][j];
                    tmp[i][j] %= p;
                    if (tmp[i][j] < 0)
                        tmp[i][j] += p;
                }
            }
        ++valid;
    }
    for (int i = 0; i < N; ++i) {
        int first = -1;
        for (int j = 0; j < M; ++j)
            if (tmp[i][j] != 0) {
                first = j;
                break;
            }
        if (first == -1) {
            if (tmp[i][M] != 0) {
                cout << "-1\n";
                exit(0);
            }
            continue;
        }
        Sol[first] = tmp[i][M];
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int a = date(), b = date();
        for (int j = 0; j < M; ++j)
            scanf("%d", Init[i] + j);
        Init[i][M] = ((b - a) % 365 + 365) % 365;
    }
    Gauss(5, Sol5);
    Gauss(73, Sol73);
    for (int i = 0; i < M; ++i) {
        cout << (146 * Sol5[i] + 220 * Sol73[i] + 364) % 365 + 1 << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
#define lg2 std::__lg
using std::cin;
using std::cout;

const int N = 400054, LN = 18, TH = 18;

int n, m, q;
int len[N], leap[N];
char s[N], t[N];
int pre[N], suf[N], bel[N];
int L, st[LN][N / TH], *lay = *st;

inline int max(const int x, const int y) {return x < y ? y : x;}

namespace SAM {
	int p, np = 1, cnt = 1;
	int pa[N], d[N][2], val[N];

	#define q d[p][x]
	int extend(int x) {
		for (p = np, val[np = ++cnt] = val[p] + 1; p && !q; q = np, p = pa[p]);
		if (!p) pa[np] = 1;
		else if (val[p] + 1 == val[q]) pa[np] = q;
		else {
			int nq = ++cnt;
			val[nq] = val[p] + 1, memcpy(d[nq], d[q], 8);
			pa[nq] = pa[q], pa[np] = pa[q] = nq;
			for (int Q = q; p && q == Q; q = nq, p = pa[p]);
		}
		return np;
	}
	#undef q
}

void build_sparse_table(int *a) {
	int i, j, k, I, *f, *g = lay;
	for (I = i = 0; I < n; ++i, I += TH) {
		pre[I] = a[I], bel[I] = i;
		for (j = 1; j < TH && I + j < n; ++j) pre[I + j] = max(pre[I + j - 1], a[I + j]), bel[I + j] = i;
		for (--j, suf[I + j] = a[I + j]; --j >= 0; suf[I + j] = max(suf[I + j + 1], a[I + j]));
		lay[i] = suf[I];
	}
	for (k = L = i, j = 0; 1 << (j + 1) <= L; ++j)
		for (f = g, g = st[j + 1], k -= 1 << j, i = 0; i < k; ++i)
			g[i] = max(f[i], f[i + (1 << j)]);
}

inline int RMQ(int x, int y) {
	if (y < x + TH) return *std::max_element(len + x, len + (y + 1));
	int xb = bel[x] + 1, yb = bel[y], c = lg2(yb - xb);
	return max(max(suf[x], pre[y]), xb < yb ? max(st[c][xb], st[c][yb - (1 << c)]) : 0);
}

int main() {
	int i, j = 0, l, r, x, y, id;
	std::ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> s >> t >> q, n = strlen(s), m = strlen(t);
	for (i = 0; i < m; ++i) SAM::extend(t[i] - 97);
	x = 1, y = 0;
	for (i = 0; i < n; ++i) {
		for (id = s[i] - 97; x && !SAM::d[x][id]; x = SAM::pa[x], y = SAM::val[x]);
		len[i] = (x ? (x = SAM::d[x][id], ++y) : (x = 1, y = 0));
	}
	for (*leap = -1, j = i = n - 1; i >= 0; --i)
		for (; j > i - len[i]; --j) leap[j] = i;
	build_sparse_table(len);
	for (; q; --q)
		cin >> l >> r,
		cout << (leap[--l] < --r ? max(leap[l] - l + 1, RMQ(leap[l] + 1, r)) : r - l + 1) << '\n';
	return 0;
}