Đến với kỳ thi HSG Tin học lần này, bạn Tùng tham gia thêm một trò chơi ngoại khóa, phần thưởng giành cho người chiến thắng là một chiếc thẻ nhớ 64GB từ Ban tổ chức. Trò chơi như sau: Ban tổ chức đưa ra một chuỗi kí tự gồm toàn các chữ cái latin in thường từ 'a' tới 'z' cùng với ~M~ câu hỏi. Mỗi câu hỏi bao gồm hai số nguyên ~l~ và ~r~, nhiệm vụ của người chơi là trả lời xem chuỗi con từ vị trí ~l~ tới vị trí ~r~ của chuỗi ban đầu có đối xứng hay không?

Yêu cầu: Hãy giúp bạn Tùng trả lời các câu hỏi để giành chiến thắng trò chơi?

Mô tả đầu vào

• Dòng đầu tiên chứa chuỗi kí tự s chỉ gồm toàn chữ cái latin in thường.
• Dòng thứ hai chứa số nguyên dương ~M~ -số câu hỏi của Ban tổ chức.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l~ và ~r~ thể hiện một câu hỏi của Ban tổ chức.

Mô tả đầu ra

• Ứng với mỗi câu hỏi, đưa ra kết quả trên một dòng: số 1 nếu như chuỗi con đó là đối xứng, ngược lại ghi số -1.

Ví dụ

Input

abxbagredcnmooojhggohoreomodioibba
5
1 5
10 23
25 27
29 31
13 15

Output

1
-1
1
1
1

Ràng buộc

• ~1≤∣s|≤10^5;1 \le M \le 10^5~, Với |s| là độ dài của chuỗi s.