Вам надається рядок \(S\), що складається з A, B, C.

Нехай \(S^{(0)}:=S\). Для \(i=1,2,3,...\) нехай \(S^{(i)}\) буде результатом одночасної заміни символів \(S^{(i-1)}\) таким чином: A → BC, B → CA, C → AB.

Відповідайте на \(Q\) запитів. \(І\)-й запит виглядає наступним чином.

• Виведіть \(k_i\)-й символ від початку \(S^{(t_i)}\).

Обмеження

• \(S\) — це рядок довжиною від 1 до \(10^5\) (включно), що складається з A, B, C.

• \(1 \leq Q \leq 10^5\)

• \(0 \leq t_i \leq 10^{18}\)

• \(1 \leq k_i \leq \min(10^{18}\), довжина \(S^{(t_i)}\))

• \(Q, t_i, k_i\) є цілими числами.

Формат вхідних даних

Перший рядок містить \(S\)

Наступний  рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять цілі числа \(t_i, k_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть для кожного запиту відповідь в окремому рядку.

Примітка

До прикладу 1:

Маємо \(S^{(0)}\) =ABC, \(S^{(1)}\) =BCCAAB.

Таким чином, відповіді на запити A, B, C, B.

Приклад вхідних даних

ABC
4
0 1
1 1
1 3
1 6

Приклад вихідних даних

A
B
C
B

Приклад вхідних даних

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

Приклад вихідних даних

A
A
C
A
A