| VK Cup 2018 - Раунд 1 |
|---|
| Закончено |
У Алисы есть строка, состоящая из букв «A», «B» и «C». Боб может использовать следующие замены для любых подстрок данной строки в любом порядке любое число раз:
- A
BC - B AC
- C AB
- AAA пустая строка
Обратите внимание, что подстрокой называется одна или более соседняя буква. Для данных запросов определите, можно ли получить конечную строку из начальной.
Первая строка содержит строку S (1 ≤ |S| ≤ 105). Вторая строка содержит строку T (1 ≤ |T| ≤ 105), каждая из этих строк содержит только заглавные латинские буквы «A», «B» и «C».
Третья строка содержит число запросов Q (1 ≤ Q ≤ 105).
Следующие Q строк описывают запросы. i-я из этих строк содержит четыре целых числа ai, bi, ci, di. Они описывают i-й запрос: возможно ли получить строку T[ci..di] из строки S[ai..bi] применением вышеописанных операций конечное число раз?
Здесь U[x..y] обозначает подстроку U, которая начинается в позиции x (нумерация с 1) и заканчивается в позиции y. В частности, U[1..|U|] — строка U целиком.
Гарантируется, что 1 ≤ a ≤ b ≤ |S| и 1 ≤ c ≤ d ≤ |T|.
Выведите строку из Q символов, где i-й символ равен «1», если ответ на i-й запрос «Да», и «0» иначе.
AABCCBAAB
ABCB
5
1 3 1 2
2 2 2 4
7 9 1 1
3 4 2 3
4 5 1 3
10011
В первом запросе мы можем получить нужную строку, например, используя следующие шаги: 
.
В третьем запросе просят получить из строки AAB строку A, но в этом случае невозможно избавиться от буквы «B».
