Xét một xâu \(S^{(0)}\) chỉ chứa các ký tự A, B và C. Với mỗi \(n \ge 0\), ta tạo ra xâu \(S^{(n+1)}\) bằng cách thay mỗi ký tự A trong \(S^{(n)}\) bằng BC, thay mỗi ký tự B bằng CA, và thay mỗi ký tự C bằng AB. Cho \(Q\) truy vấn dạng \((t_i, k_i)\), bạn hãy viết chương trình trả lời xem ký tự thứ \(k_i\) của xâu \(S^{(t_i)}\) là A, B, hay C nhé!

Input

• Dòng đầu chứa xâu \(S_0\) có độ dài tối đa là \(10^5\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) không vượt quá \(10^5\).
• Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(t_i\) và \(k_i\). Dữ liệu đảm bảo \(0 \le t_i \le 10^{18}\) và \(1 \le k_i\le min\left(10^{18}, \left|S^{(t_i)}\right|\right)\).

Output

• In ra \(Q\) dòng là đáp số cho từng truy vấn tương ứng.

Ví dụ

Sample input 01

CBA
6
0 1
1 1
2 1
2 2
2 3
2 6

Sample output 01

C
A
B
C
C
B

Giải thích

Ta có \(S^{(0)}=\)CBA, \(S^{(1)}=\)ABCABC, \(S^{(2)}=\)BCCAABBCCAAB.