小 A tài giỏi được chọn làm người ra đề cho ION2018. Bây giờ cậu cần giải quyết vấn đề đặt tên bài toán.
Mô tả bài toán
小 A được chọn làm người ra đề cho ION2018. Cậu đã chuẩn bị kỹ lưỡng một bài toán có chất lượng rất cao và đã hoàn thành mọi công việc ngoài việc đặt tên bài toán.
Vì ION đã được tổ chức nhiều năm nên việc đặt tên bài toán cũng có quy định. Sổ tay ra đề ION quy định: mỗi năm, hội đồng ra đề xác định một xâu gồm các chữ cái thường, gọi là xâu đặt tên của năm đó. Tên của mỗi bài toán phải là một xâu con liên tiếp không rỗng của xâu đặt tên năm đó và không được trùng với tên của bất kỳ bài toán nào trong năm trước.
Vì một số lý do đặc biệt, 小 A không biết tên của từng bài toán ở ION2017, nhưng bằng một số cách đặc biệt, cậu đã có được xâu đặt tên của ION2017. Bây giờ 小 A có $Q$ truy vấn: mỗi truy vấn cho xâu đặt tên của ION2017 và xâu đặt tên của ION2018, hãy tìm số cách đặt tên bài toán sao cho tên đó chắc chắn thỏa mãn quy định của hội đồng ra đề, tức là một xâu con liên tiếp không rỗng của xâu đặt tên ION2018 và chắc chắn không trùng với tên của bất kỳ bài toán nào ở ION2017.
Vì một số lý do đặc biệt, các xâu đặt tên ION2017 được cho trong mọi truy vấn đều là xâu con liên tiếp của một xâu nào đó. Chi tiết xem phần dữ liệu vào.
Dữ liệu vào
Dòng đầu tiên chứa một xâu $S$. Các xâu đặt tên ION2017 trong những truy vấn sau đều là xâu con liên tiếp của $S$.
Dòng thứ hai chứa một số nguyên dương $Q$, biểu diễn số truy vấn.
Trong $Q$ dòng tiếp theo, mỗi dòng chứa một xâu $T$ và hai số nguyên dương $l,r$, biểu diễn truy vấn: nếu xâu đặt tên ION2017 là $S[l..r]$ và xâu đặt tên ION2018 là $T$, có bao nhiêu cách đặt tên chắc chắn thỏa mãn quy định?
Bảo đảm các xâu được cho trong dữ liệu vào đều gồm chữ cái thường.
Dữ liệu ra
In $Q$ dòng. Dòng thứ $i$ chứa một số nguyên không âm biểu diễn đáp án cho truy vấn thứ $i$.
Ví dụ
Dữ liệu vào 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Dữ liệu ra 1
12 10 4
Ví dụ 2
Xem name/name2.in và name/name2.ans trong thư mục của thí sinh.
Nhiệm vụ con
| Bộ kiểm thử | $|S|\le$ | $Q\le$ | $\sum |T|\le$ | Ràng buộc truy vấn | Ràng buộc khác |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | Với mọi truy vấn, $l=1,r=|S|$ | $|T|\le 200$ |
| $2$ | $1000$ | ||||
| $3$ | |||||
| $4$ | $5*10^5$ | Không có | |||
| $5$ | |||||
| $6$ | $5*10^5$ | $1$ | |||
| $7$ | |||||
| $8$ | $10^5$ | $10^5$ | $2*10^5$ | ||
| $9$ | Xâu ngẫu nhiên | ||||
| $10$ | $2*10^5$ | $4*10^5$ | Không có | ||
| $11$ | Xâu ngẫu nhiên | ||||
| $12$ | $3*10^5$ | $6*10^5$ | Không có | ||
| $13$ | Xâu ngẫu nhiên | ||||
| $14$ | $4*10^5$ | $8*10^5$ | Không có | ||
| $15$ | Xâu ngẫu nhiên | ||||
| $16$ | $5*10^5$ | $10^6$ | Không có | ||
| $17$ | Xâu ngẫu nhiên | ||||
| $18$ | $2*10^5$ | Không có | Không có | ||
| $19$ | $3*10^5$ | ||||
| $20$ | $4*10^5$ | ||||
| $21$ | $5*10^5$ | ||||
| $22$ | |||||
| $23$ | |||||
| $24$ | |||||
| $25$ |
Với mọi dữ liệu, bảo đảm $1\le l\le r\le |S|$, $1\le |T|\le 5*10^5$.