T140934 三色球 (hard version)

到了 $2035$ 年，双色球已经被时代抛弃，转而变为新的三色球引领彩票发展。

彩票公司首先会生成一个长度为 $|s|$ 的三色球序列 $s$，也就是一个仅由 `RGB` （Red Green Blue）三种颜色构成的一个字符串。接着这个三色球序列会进行若干次变化。每次变化我们通过相邻的两个球生成一个新球排在下方，就可以以当前三色球序列 $str$ 为模板形成一个长度为 $|str|-1$ 的三色球序列 $str'$。 相邻的两个球生成一个新球，具体的规则如下： | 左侧球\右侧球 | R | G | B | | :----------: | :----------: | :----------: | :----------: | | **R** | R | B | G | | **G** | B | G | R | | **B** | G | R | B | 简单来说就是：“同色得同色，异色得异色”。 为了方便理解，以下是 `RGB` 进行 $2$ 次变化的具体例子：  ``` R G B B R G ``` 容易发现**三色球序列 $str$ 通过 $|str|-1$ 次变换可以得到一个唯一确定的球**。而彩票中奖的方式就与这个变换有关： 彩票公司给定了三色球序列 $s$ 之后，指定 $q$ 组询问，每组询问形如：如果把三色球序列的一个下标连续的子序列 $str[l:r]$ 提出来，对它进行变化直到剩下一个球，这个球的颜色是什么？ 容易发现瞎蒙全部猜中的概率为 $\dfrac{1}{3^q}$，鲜有人获奖。所以你决定在 $1s$ 内回答所有问题，让彩票公司破产。

输入第一行一个字符串 $s$ ，表示彩票公司一开始生成的三色球序列。 输入第二行一个整数 $q$ ，表示彩票公司的询问组数。 接下来 $q$ 行，每行两个整数 $l,r$ 描述一组询问。

输出共一行 $q$ 个字符，即对于每一个询问的答案。

### 数据范围 对于 $100\%$ 的数据，满足 $1\le |s|,q\le 5\times 10^4$，$1\le l\le r\le |s|$ 。