Xác định xâu con \(x\) của xâu \(y\) biết \(x\) gồm các ký tự trong đoạn chỉ số \([L;R)\) của \(y\) (từ \(L\) tới \(R\), nhưng không bao gồm \(R\))

Cho một xâu kí tự \(y\) chỉ gồm các kí tự latin viết thường có thể chứa dấu cách. Có \(N\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L, R\) \((0\le L \le R < \texttt{len}(y))\).

Yêu cầu: với mỗi truy vấn, in ra xâu con của xâu \(y\) từ chỉ số \(L\) tới chỉ số \(R\)?

Input

• Dòng đầu ghi xâu y có độ dài không quá \(10^6\); xâu gồm các kí tự latin và số.

• Dòng thứ hai ghi số nguyên \(N\) là số lượng truy vấn \((1\le N\le 100)\)

• \(N\) dòng tiếp theo mỗi dòng ghi hai số nguyên \(L, R\)

Output

• Với mỗi truy vấn, in ra xâu con từ chỉ số \(L\) đến chỉ số \(R\) của xâu

Example

0123456 
3 
2 5 
2 3 
0 7 

234 
2 
0123456