Determining Nucleotide Assortments

Genes 'R Us analyzes DNA strands to find anomalies, matches, patterns, or other specific items its customers want. You may recall from high school biology that a DNA molecule consists of two chains wrapped around each other to form the double helix. Each chain is made of four types of nucleotides, distinguished by their nitrogen bases: adenine (A), thymine (T), guanine (G), and cytosine (C).

A recent customer of Genes 'R Us wants to quickly determine which of the four nucleotide types is most prevalent in a given section of DNA, and which are second, third, and fourth most prevalent. A strand may contain tens of thousands of nucleotides, and the customer will ask about many sections of the same strand. Your task is to write an efficient program that answers these queries.

The first line is a string describing a DNA strand. It consists only of the characters A, T, G, and C, and its length $n$ satisfies $n \leq 50\,000$. The next line contains a positive integer $m$ ($m \leq 25\,000$), the number of sections to investigate. The following $m$ lines each contain a pair of integers $s_i$ and $e_i$, the start and end positions of a section, where $1 \leq s_i \leq e_i \leq n$. The two integers in each pair are separated by a single space.

For each section, output one line containing a permutation of ATGC. The first character is the most prevalent nucleotide in the section, the second character is the second most prevalent, and so on. If nucleotides occur equally often, order them by ATGC: A comes before T, G, and C, and T comes before G and C.