Độ đẹp của dải giấy

Cho một dãy gồm $n$ mảnh giấy xếp cạnh nhau, đánh số từ $1$ đến $n$ từ trái sang phải. Mảnh thứ $i$ có màu $s_i$, là một chữ cái thường trong bảng chữ cái tiếng Anh.

Với một màu $c$ và một số nguyên $m$, ta được phép sơn lại tối đa $m$ mảnh bất kỳ, mỗi mảnh sơn thành một màu tùy ý (vẫn là một chữ cái thường). Sau khi sơn, xét tất cả các đoạn con liên tiếp mà mọi mảnh trong đoạn đều có màu $c$; độ đẹp ứng với $(m,c)$ là độ dài lớn nhất trong các đoạn đó.

Bạn nhận được $q$ truy vấn, mỗi truy vấn gồm một số nguyên $m_i$ và một màu $c_i$. Với mỗi truy vấn, hãy tính độ đẹp lớn nhất đạt được khi sơn lại tối đa $m_i$ mảnh, xét theo màu $c_i$. Các truy vấn độc lập với nhau: mỗi truy vấn đều xuất phát từ dãy ban đầu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số mảnh giấy.
• Dòng thứ hai chứa xâu $s$ gồm $n$ chữ cái thường, mô tả màu ban đầu của các mảnh.
• Dòng thứ ba chứa số nguyên $q$ là số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $m_i$ và một chữ cái thường $c_i$, cách nhau bởi dấu cách.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là độ đẹp lớn nhất đạt được ứng với truy vấn thứ $i$.

Ràng buộc

• $1\le n\le 1500$
• $1\le q\le 200000$
• $1\le m_i\le n$
• $s_i,c_i$ là các chữ cái thường trong bảng chữ cái tiếng Anh.

Ví dụ