Xâu đối xứng

Tham dự thi trại hè lần này, bạn Sơn Tùng đăng ký tham dự trò chơi RCV, phần thưởng cho người chiến thắng là một chiếc thẻ nhớ 16GB từ ban tổ chức (BTC). Trò chơi như sau: BTC đưa ra một chuỗi các ký tự chỉ bao gồm các chữ cái in thường từ a đến z, và một số bộ $l,r$. Người chơi sẽ trả lời một bộ các câu hỏi của BTC có dạng: xâu con nhận được kể từ vị trí $l$ đến vị trí $r$ có đối xứng hay không?

Các ký tự của xâu được đánh số từ $1$. Xâu con từ vị trí $l$ đến vị trí $r$ gồm các ký tự $s_l{s}_{l+1}\dots s_r$; xâu này đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau (xâu một ký tự luôn đối xứng).

Bạn hãy giúp Sơn Tùng giành chiến thắng cuộc thi này.

Dữ liệu vào

• Dòng đầu ghi xâu ký tự $s$ (không cho biết độ dài).
• Dòng tiếp theo ghi số nguyên $k$ là số câu hỏi của BTC.
• $k$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $l,r$.

Dữ liệu ra

Gồm $k$ dòng, mỗi dòng ghi tương ứng câu trả lời: nếu xâu con từ vị trí $l$ đến vị trí $r$ đối xứng thì ghi 1, ngược lại ghi -1.

Ràng buộc

• $1\le |s|\le {10}^5$, $s$ chỉ gồm các chữ cái in thường từ a đến z.
• $1\le k\le {10}^5$.
• $1\le l\le r\le |s|$.
• $30\%$ số test có $|s|\le 100$.
• $30\%$ số test khác có $|s|\le {10}^3$.

Ví dụ