Сенсацией завершился очередной съезд британских учёных, проходивший в городе Баш. Профессор Надувайло Д.В. выступил с докладом, во многом меняющим современное представление о мире.

Ранее считалось, что молекулы ДНК человека и животных состоят из четырёх нуклеотидов, обозначаемых символами «A», «C», «G», «T». Однако профессор Надувайло доказал, что у каждого нуклеотида существует соответствующий ему антинуклеотид, который также может входить в состав молекулы ДНК. Антинуклеотиды профессор обозначил символами «a», «c», «g», «t», причём буквой «a» он обозначил антинуклеотид для «A», буквой «c» — антинуклеотид для «C» и т. д.

Кроме того, в ходе исследований профессор заметил, что строки ДНК человека имеют особое строение. Профессор считает, что человеческая строка ДНК — это либо пустая строка, либо конкатенация двух человеческих строк (то есть одна человеческая строка, приписанная в конец другой), либо человеческая строка, в начало которой добавлен некоторый нуклеотид, а в конец — соответствующий ему антинуклеотид. Например, строки «CcAaGg» и «ACca» являются человеческими, а «cC» и «GTgt» — нет.

Профессор Надувайло предположил, что для установления степени родства человека и животного достаточно лишь проверить, являются ли человеческими некоторые подстроки строки ДНК этого животного. Чтобы разработать эффективный способ проведения таких проверок, коллектив британских учёных пригласил лучших программистов, то есть вас.

В первой строке записана строка ДНК некоторого животного, состоящая из символов «A», «C», «G», «T», «a», «c», «g», «t» и имеющая длину L (1 ≤ L ≤ 100000). Во второй строке записано целое число q — количество подстрок данной строки, которые требуется проверить (1 ≤ q ≤ 50000). В i-й из следующих q строк через пробел записаны целые числа l_i и r_i — номер первого и последнего символа проверяемой подстроки (1 ≤ l_i ≤ r_i ≤ L).

Выведите строку длины q, состоящую из символов «0» и «1». i-й символ должен быть равен единице, если подстрока, начинающаяся в позиции l_i и заканчивающаяся в позиции r_i, является человеческой, и нулю в противном случае.