Phát hiện điểm bất thường là một vấn đề đã được nghiên cứu kỹ lưỡng có liên quan đến một số lĩnh vực khoa học, chẳng hạn như tim mạch để phát hiện nhịp tim bất thường, quy trình sản xuất để đảm bảo chất lượng sản phẩm, quản lý hoạt động của trung tâm dữ liệu để theo dõi tình trạng phần cứng và phần mềm, và vật lý thiên văn để loại bỏ các tín hiệu nhiễu tạm thời khỏi các phép đo giao thoa kế sóng hấp dẫn. Đối với trường hợp cụ thể của chuỗi và chuỗi dữ liệu, ta quan tâm đến việc xác định các chuỗi con bất thường, trong đó các giá trị ngoại lệ không chỉ là các giá trị đơn lẻ mà là một chuỗi các giá trị. Việc phát hiện bất thường của chuỗi con cho phép xác định sớm các sự kiện bất thường tiềm ẩn mà nếu không sẽ không được phát hiện.

Ta xem xét ứng dụng của chúng trong việc phát hiện bất thường các phản hồi liên quan tới việc gửi và nhận của các cảm biến. Thông tin giao tiếp giữa hai cảm biến ban đầu là một xung điện, sau đó được mã hóa thành các chuỗi gồm các chữ cái thường. Một trong những dạng dị thường là mất một đoạn ký tự ở đầu hoặc cuối chuỗi dữ liệu.

Độ khó khăn của mô hình được mô tả trên có thể được chứng minh thông qua việc liệt kê tất cả các chuỗi khác rỗng khác nhau có thể có sau khi tiến hành bỏ một đoạn ký tự ở đầu hoặc cuối chuỗi (có thể không bỏ đoạn ký tự nào). Bạn là một cộng tác viên của nhóm nghiên cứu, hãy giúp nhóm liệt kê ra các chuỗi khác nhau từ hàng loạt chuỗi được sinh ra từ việc trích một phần chuỗi liên tục từ chuỗi gốc được cung cấp.

Yêu cầu: Với mỗi chuỗi liên tục được trích ra từ chuỗi gốc, hãy xác định số lượng chuỗi khác rỗng khác nhau có thể có sau khi tiến hành bỏ một đoạn ký tự ở đầu hoặc cuối chuỗi (có thể không bỏ đoạn ký tự nào) của chuỗi liên tục đó.

Input

• Dòng đầu tiên chứa số nguyên ~N~ và ~Q~ lần lượt là độ dài của chuỗi gốc và số lượng chuỗi liên tục được trích ra (~1 \le N \le 2 \times 10^5~, ~1 \le Q \le 2 \times 10^5~).
• Dòng tiếp theo chứa một chuỗi ~S~ có độ dài ~N~ bao gồm các chữ cái thường.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le Q~) thể hiện hai giá trị ~l_i~ và ~r_i~ thể hiện một chuỗi liên tục được trích ra từ chuỗi gốc bằng cách lấy các ký tự liên tục từ vị trí ~l_i~ đến vị trí ~r_i~ (~1 \le l_i \le r_i \le N~).

Output

• Với mỗi truy vấn, in ra một dòng chứa một số nguyên duy nhất là số lượng chuỗi khác rỗng khác nhau tìm được.