Genes ’R Us 专门从事 DNA 链的分析，以寻找异常、匹配、模式或其客户感兴趣的任何特定项目。你可能还记得高中生物学知识，DNA 分子由两条相互缠绕的链组成，形成众所周知的双螺旋结构。这些链由四种不同类型的核苷酸组成，每种核苷酸由特定的含氮碱基区分：腺嘌呤 (A)、胸腺嘧啶 (T)、鸟嘌呤 (G) 和胞嘧啶 (C)。

Genes ’R Us 的一位新客户希望能够快速确定在给定的 DNA 片段中，哪种类型的核苷酸出现频率最高，以及第二、第三和第四频繁的核苷酸分别是哪种。对于给定的 DNA 链（可能包含数万个核苷酸），可能存在许多需要此类信息的片段。你被要求编写一个高效的程序来回答这些问题。

输入格式

输入以一个描述 DNA 链的字符串开始。该字符串由字符 A、T、G 和 C 组成，长度为正整数 $n \le 50\,000$。下一行包含一个正整数 $m$ ($m \le 25\,000$)，表示需要调查的 DNA 链片段数量。接下来是 $m$ 行，每行包含一对整数 $s_i$ 和 $e_i$，分别表示片段的起始和结束位置，其中 $1 \le s_i \le e_i \le n$。整数对之间由单个空格分隔。

输出格式

对于每个片段，输出一行包含 ATGC 的排列，其中第一个字符表示该片段中出现频率最高的核苷酸，第二个字符表示第二频繁的核苷酸，依此类推。如果出现频率相同，则按照 ATGC 的顺序打破平局（即，如果出现次数相同，A 排在 T、G 或 C 之前；T 排在 G 或 C 之前，以此类推）。

样例

样例输入 1

TATATGCTCT
3
1 10
6 10
6 6

样例输出 1

TACG
TCGA
GATC