Khoảng cách

Điền 26 kí tự Tiếng Anh in thường theo thứ tự từ điển thành một vòng tròn cách đều nhau 1 đơn vị như hình bên. Khoảng cách giữa hai kí tự là số bước di chuyển ngắn nhất từ kí tự này đến kí tự kia. Ví dụ khoảng cách giữa hai kí tự 'a' và 'c'; khoảng cách giữa 'a' và 'z' là 1.

Khoảng cách của một xâu là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu đó. Ví dụ tính khoảng cách của xâu "adc":

• Khoảng cách của 'a' và 'd' là 3.
• Khoảng cách của 'a' và 'c' là 2.
• Khoảng cách của 'd' và 'c' là 1.

Vậy khoảng cách của xâu 'adc' là $\max(3, 2, 1) = 3$.

Cho xâu $S$ gồm $N$ kí tự được đánh chỉ số từ 1 đến $N$ và $Q$ truy vấn, mỗi truy vấn yêu cầu tính khoảng cách của xâu con từ vị trí $L$ đến vị trí $R$ trong xâu $S$ ($1 \le L \le R \le N$).

Dữ liệu vào từ file văn bản KHOANGCACH.INP:

• Dòng đầu tiên chứa xâu $S$ chỉ gồm các kí tự Tiếng Anh in thường gồm $N$ kí tự ($1 \le N \le 10^5$).
• Dòng thứ hai chứa số nguyên dương $Q$ ($Q \le 10^5$).
• $Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $L, R$ ($1 \le L \le R \le N$) mô tả đoạn con của xâu $S$ cần tính khoảng cách.

Kết quả ghi ra file văn bản KHOANGCACH.OUT: Gồm $Q$ dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.

• Có 50% số test ứng với 50% số điểm có $Q = 1; N \le 10^3$.
• 20% số test tiếp theo ứng với 20% số điểm có $Q = 1$.
• 20% số test tiếp theo ứng với 20% số điểm có $N \le 10^3$.
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.