Độ Phủ Chuỗi Con

Tác giả:

Dạng bài

Điểm: 2500 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một xâu ký tự \(S\) có độ dài \(N\) chỉ gồm các chữ cái tiếng Anh in thường. Một xâu con của \(S\) là một chuỗi các ký tự liên tiếp xuất hiện trong \(S\).

Với mỗi xâu con khác rỗng \(w\) của \(S\), giả sử tập hợp tất cả các vị trí kết thúc của các lần xuất hiện của \(w\) trong \(S\) là:

\[\mathcal{E}(w) = \{p_1, p_2, \dots, p_k\} \quad (1 \le p_1 < p_2 < \dots < p_k \le N)\]

Số lần xuất hiện của \(w\) trong \(S\) được ký hiệu là \(\operatorname{occ}(w) = k = |\mathcal{E}(w)|\).

Ta định nghĩa độ phủ (coverage) của xâu con \(w\), ký hiệu là \(\operatorname{cov}(w)\), là tổng số vị trí trên xâu \(S\) được bao phủ bởi ít nhất một lần xuất hiện của \(w\):

\[\operatorname{cov}(w) = \left| \bigcup_{i=1}^k [p_i - |w| + 1, p_i] \right|\]

Trọng số của xâu con \(w\) được tính theo công thức:

\[\mathcal{W}(w) = \operatorname{cov}(w) \times \operatorname{occ}(w)\]

Cho \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)). Bạn cần tính tổng trọng số của tất cả các xâu con phân biệt \(w\) của \(S\) thỏa mãn số lần xuất hiện của \(w\) nằm trong đoạn \([L, R]\):

\[\sum_{\substack{w \in \operatorname{Sub}(S) \\ L \le \operatorname{occ}(w) \le R}} \mathcal{W}(w) \pmod{998244353}\]

trong đó \(\operatorname{Sub}(S)\) là tập hợp tất cả các xâu con khác rỗng phân biệt của \(S\).

Input

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) — lần lượt là độ dài của xâu \(S\) và số lượng truy vấn.
Dòng thứ hai chứa xâu ký tự \(S\) có độ dài \(N\) chỉ gồm các chữ cái tiếng Anh in thường ('a' đến 'z').
Trong \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)) mô tả một truy vấn.

Output

Với mỗi truy vấn, in ra trên một dòng một số nguyên duy nhất là kết quả tìm được theo modulo \(998244353\).

Example

Test 1

Input

6 4
ababaa
1 6
2 3
1 1
3 6

Output

Note

Các xâu con phân biệt của \(S = \text{"ababaa"}\) và trọng số tương ứng:

\(\text{"a"}\): xuất hiện tại \(\{1, 3, 5, 6\}\), \(\operatorname{occ} = 4\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 4 = 16\).
\(\text{"b"}\): xuất hiện tại \(\{2, 4\}\), \(\operatorname{occ} = 2\), \(\operatorname{cov} = 2\), trọng số \(\mathcal{W} = 2 \times 2 = 4\).
\(\text{"ab"}\): xuất hiện tại \(\{2, 4\}\), \(\operatorname{occ} = 2\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 2 = 8\).
\(\text{"ba"}\): xuất hiện tại \(\{3, 5\}\), \(\operatorname{occ} = 2\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 2 = 8\).
\(\text{"aa"}\): xuất hiện tại \(\{6\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 2\), trọng số \(\mathcal{W} = 2 \times 1 = 2\).
\(\text{"aba"}\): xuất hiện tại \(\{3, 5\}\), \(\operatorname{occ} = 2\), \(\operatorname{cov} = 5\), trọng số \(\mathcal{W} = 5 \times 2 = 10\).
\(\text{"bab"}\): xuất hiện tại \(\{4\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 3\), trọng số \(\mathcal{W} = 3 \times 1 = 3\).
\(\text{"baa"}\): xuất hiện tại \(\{6\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 3\), trọng số \(\mathcal{W} = 3 \times 1 = 3\).
\(\text{"abab"}\): xuất hiện tại \(\{4\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 1 = 4\).
\(\text{"baba"}\): xuất hiện tại \(\{5\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 1 = 4\).
\(\text{"abaa"}\): xuất hiện tại \(\{6\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 4\), trọng số \(\mathcal{W} = 4 \times 1 = 4\).
\(\text{"ababa"}\): xuất hiện tại \(\{5\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 5\), trọng số \(\mathcal{W} = 5 \times 1 = 5\).
\(\text{"babaa"}\): xuất hiện tại \(\{6\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 5\), trọng số \(\mathcal{W} = 5 \times 1 = 5\).
\(\text{"ababaa"}\): xuất hiện tại \(\{6\}\), \(\operatorname{occ} = 1\), \(\operatorname{cov} = 6\), trọng số \(\mathcal{W} = 6 \times 1 = 6\).

Tổng trọng số tất cả các xâu con phân biệt là \(16 + 4 + 8 + 8 + 2 + 10 + 3 + 3 + 4 + 4 + 4 + 5 + 5 + 6 = 82\)... (lưu ý tính đúng công thức các đoạn giao nhau).

Scoring

Subtask 1 (30 điểm): \(N \le 50\), \(Q \le 50\).
Subtask 2 (25 điểm): \(N \le 300\), \(Q \le 300\).
Subtask 3 (20 điểm): \(S\) chỉ gồm duy nhất một loại ký tự (ví dụ \(S = \text{"aaaa...a"}\)), \(N \le 10^5\), \(Q \le 10^5\).
Subtask 4 (15 điểm): \(N \le 3000\), \(Q \le 3000\).
Subtask 5 (10 điểm): \(N \le 10^5\), \(Q \le 10^5\).

Bình luận

Tải bình luận...

Không có bình luận nào.