Vẫn là câu chuyện Hậu Nghệ xạ nhật, tuy nhiên ở phiên bản này, 9 mặt trời lại là 9 người con của Ngọc Hoàng. Do giết con của Ngọc Hoàng nên từ thần bất tử, Hậu Nghệ và Hằng Nga bị đày xuống hạ giới. Sau vô vàn nỗ lực, Hậu Nghệ đã tìm thấy viên thuốc bất tử và cất trong hộp ở nhà, dặn vợ không được mở ra. Tuy nhiên, cũng như Pandora trong thần thoại Hy Lạp, Hằng Nga đã nhân lúc chồng không có nhà mà lén mở hộp ra. Đúng lúc này, Hậu Nghệ quay về. Sợ chồng phát hiện nên Hằng Nga bỏ luôn viên thuốc vào miệng. Ngay lập tức, Hằng Nga bay lên trời do công hiệu viên thuốc quá mạnh, do chỉ cần nửa viên thì đã có thể bất tử.

Lúc này, Heo nhớ ra trong game Chuối Cụ ở bài 1, để có thể tăng gấp đôi công hiệu của lá thuốc, cậu có thể gacha mở rương hoặc sử dụng gift code. Heo đã dùng toàn bộ số tiền của mình để đi du lịch các nước, tìm hiểu sự tích và chơi các trò chơi nên không thể nạp thêm để gacha như Tuab, nhưng Heo có thể sử dụng một gợi ý của nhà phát hành game để nhập gift code.

Gợi ý của nhà phát hành game gồm một xâu ~S~ chỉ gồm các con số từ ~0~ đến ~9~. Ngoài ra, Heo còn được thưởng thêm ~q~ cặp số ~l~, ~p~. Biết rằng gift code được kích hoạt nếu bạn nhập đúng ~q~ chữ số, chữ số thứ ~i~ là kí tự ~p~ của xâu con~^\dagger~ có thứ tự từ điền lớn nhất của ~S~ trong các xâu con có độ dài ~l~.

Input

Vào từ file văn bản BAI4.inp:

• Dòng đầu chứa xâu ~s~ độ dài ~n~.
• Dòng tiếp theo chứa số nguyên ~q~ ~-~ số lượng truy vấn.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, p~ mô tả một truy vấn yêu cầu tìm chữ số ~p~ trong xâu đại độ dài ~l~ của ~s~.

Output

Ghi ra file văn bản BAI4.out:

• Ghi ra ~q~ dòng, dòng thứ ~i~ ~(1 \leq i \leq q)~ ghi một chữ số là câu trả lời cho truy vấn thứ ~i~.

Scoring

Example

Sample Input

27122023
5
1 1
2 1
2 2
3 2
4 2

Sample Output

7
7
3
2
2

Note

~\dagger~ Xâu con của một xâu ban đầu có thể thu được bằng cách xóa đi một số kí tự (có thể không xóa) và giữ nguyên thứ tự các kí tự còn lại. Ví dụ ~322095~ là xâu con của ~4253574268526094254~, ~123~ là xâu con của ~123~ nhưng ~213~ không phải là xâu con của ~1231~.