Chuỗi nén có dạng: \(N = x_1 C_1 x_2 C_2 \dots x_K C_K\) là mô tả chuỗi ban đầu \(S\) có \(x_1\) kí tự \(C_1\), sau đó \(x_2\) kí tự \(C_2\), \(\dots\), \(x_K\) kí tự \(C_K\) (\(1 \le x_i \le 10^9\); \(C_i\) là các kí tự tiếng Anh từ A đến Z). Ví dụ: \(N =\) 1A5D2A thì chuỗi ban đầu \(S =\) ADDDDDDAA.

Yêu cầu: Cho chuỗi nén \(N\) và hai số tự nhiên \(L, R\). Hãy đếm xem từ vị trí \(L\) đến vị trí \(R\) của chuỗi kí tự \(S\), kí tự xuất hiện nhiều nhất bao nhiêu lần? (Vị trí trong chuỗi kí tự \(S\) được đánh số từ \(1\) đến \(|S|\), trong đó \(|S|\) là độ dài xâu \(S\)).

Input

• Dòng đầu tiên chứa chuỗi kí tự \(N\) có độ dài không quá \(10^4\);
• Dòng thứ hai chứa số nguyên dương \(L\);

• Dòng thứ ba chứa số nguyên dương \(R\).

• Dữ liệu đảm bảo \(|S| \le 10^{12}\); \(L \le R \le |S|\).

Output

• Ghi ra một số tự nhiên là kết quả của bài toán.

Example

1A5D2A
6
8

2

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có điều kiện: \(x_i < 10\).
• \(30\%\) số test khác tương ứng với \(30\%\) số điểm có điều kiện: \(|S| \le 10^4\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm không có điều kiện gì thêm.