ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1724. Тайна происхождения человека

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Сенсацией завершился очередной съезд британских учёных, проходивший в городе Баш. Профессор Надувайло Д.В. выступил с докладом, во многом меняющим современное представление о мире.
Ранее считалось, что молекулы ДНК человека и животных состоят из четырёх нуклеотидов, обозначаемых символами «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 строк через пробел записаны целые числа li и ri — номер первого и последнего символа проверяемой подстроки (1 ≤ liriL).

Результат

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

Пример

исходные данныерезультат
caAgtGTtgAacCc
5
2 3
6 9
10 11
1 14
13 14
01101
Автор задачи: Алексей Самсонов (подготовка — Иван Бурмистров)
Источник задачи: Уральская региональная командная олимпиада по программированию 2009