ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1724. Origin of Man Clarified

Time limit: 0.5 second
Memory limit: 64 MB
A conference of British scientists in the city of Bash ended with a sensation. Professor D. Cheatillo presented a talk that changed the modern idea of the world.
It was assumed earlier that DNA molecules of humans and animals consisted of four nucleotides only, which were denoted by the symbols “A”, “C”, “G”, and “T”. However, Professor Cheatillo proved that for each nucleotide there was the matching antinucleotide, which could also be present in a DNA molecule. Professor denoted the antinucleotides by the symbols “a”, “c”, “g”, and “t”, where “a” was the antinucleotide for “A”, “c” was the antinucleotide for “C”, and so on.
Moreover, the investigation carried out by Cheatillo showed that human DNA strands had special structure. Professor believes that each human DNA strand is either an empty string, or the concatenation of two human strands (i.e. a human strand followed by a human strand), or a human strand preceded by some nucleotide and followed by the matching antinucleotide. For example, the strands “CcAaGg” and “ACca” are human and the strands “cC” and “GTgt” are not.
Professor Cheatillo conjectures that the degree of the affinity between a human and an animal can be established by checking whether some substrings of a DNA strand of this animal are human. In order to develop an efficient method of performing such checks, British scientists invited the best programmers, which means you.

Input

The first line contains a DNA strand of some animal. The line consists of the symbols “A”, “C”, “G”, “T”, “a”, “c”, “g”, “t” and has length L (1 ≤ L ≤ 100000). The second line contains the number q of substrings of this line that must be checked (1 ≤ q ≤ 50000). The i-th of the following q lines contains space-separated integers li and ri, which are the numbers of the first and the last symbols of the substring that must be checked (1 ≤ liriL).

Output

Output a string of length q consisting of symbols “0” and “1”. The i-th symbol must be “1” if the substring starting at position li and ending at position ri is human. Otherwise, this symbol must be “0”.

Sample

inputoutput
caAgtGTtgAacCc
5
2 3
6 9
10 11
1 14
13 14
01101
Problem Author: Alex Samsonov (prepared by Ivan Burmistrov)
Problem Source: Ural Regional School Programming Contest 2009