Олимпиадный тренинг

Задача . D. Выбор строк

Задача

Темы: Строки Конструктив реализация *2500

У Алисы есть строка, состоящая из букв «A», «B» и «C». Боб может использовать следующие замены для любых подстрок данной строки в любом порядке любое число раз:

A $\text{[math]}$ BC
B $\text{[math]}$ AC
C $\text{[math]}$ AB
AAA $\text{[math]}$ пустая строка

Обратите внимание, что подстрокой называется одна или более соседняя буква. Для данных запросов определите, можно ли получить конечную строку из начальной.

Входные данные

Первая строка содержит строку S (1 ≤ |S| ≤ 10⁵). Вторая строка содержит строку T (1 ≤ |T| ≤ 10⁵), каждая из этих строк содержит только заглавные латинские буквы «A», «B» и «C».

Третья строка содержит число запросов Q (1 ≤ Q ≤ 10⁵).

Следующие Q строк описывают запросы. i-я из этих строк содержит четыре целых числа a_i, b_i, c_i, d_i. Они описывают i-й запрос: возможно ли получить строку T[c_i..d_i] из строки S[a_i..b_i] применением вышеописанных операций конечное число раз?

Здесь U[x..y] обозначает подстроку U, которая начинается в позиции x (нумерация с 1) и заканчивается в позиции y. В частности, U[1..|U|] — строка U целиком.

Гарантируется, что 1 ≤ a ≤ b ≤ |S| и 1 ≤ c ≤ d ≤ |T|.

Выходные данные

Выведите строку из Q символов, где i-й символ равен «1», если ответ на i-й запрос «Да», и «0» иначе.

Примечание

В первом запросе мы можем получить нужную строку, например, используя следующие шаги: $\text{[math]}$ .

В третьем запросе просят получить из строки AAB строку A, но в этом случае невозможно избавиться от буквы «B».

Примеры

№	Входные данные	Выходные данные
1	AABCCBAAB ABCB 5 1 3 1 2 2 2 2 4 7 9 1 1 3 4 2 3 4 5 1 3	10011

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++	2

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет