Bình muốn kiểm tra xem xâu con \(S[l \ldots r]\) của xâu \(S\) có phải là xâu đối xứng (palindrome) hay không. Có \(Q\) truy vấn, mỗi truy vấn yêu cầu kiểm tra xâu con \([l, r]\) (đánh số từ 0). Hãy dùng hash xâu (xuôi và ngược) để trả lời nhanh.

Định dạng đầu vào

• Dòng đầu chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng thứ hai chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(l, r\) (\(0 \le l \le r < |S|\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra YES nếu xâu con là palindrome, ngược lại in ra NO.

Ví dụ

Input:

abacaba
4
0 6
0 2
1 3
2 4

Output:

YES
YES
NO
YES

Ràng buộc

• 30% số điểm: \(|S| \le 1000, Q \le 1000\).
• 70% số điểm còn lại: \(|S|, Q \le 10^5\).