三角符文(hard version)

题号：NC296287
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的困难版本，本题无额外限制。

$\hspace{15pt}$ 有一个边长为 $n$ 的三角矩阵，一共 $n$ 行，第 $i \left(1\leq i\leq n\right)$ 行有 $i$ 个字符（类似于杨辉三角）。形如下方公式所示：
$\begin{array}{c} x_{1,1}\\ x_{2,1} \hspace{20pt} x_{2,2} \\ x_{3,1} \hspace{20pt} x_{3,2} \hspace{20pt} x_{3,3} \\ \vdots \hspace{35pt} \vdots \hspace{35pt} \vdots \hspace{35pt} \vdots \\ x_{n,1} \hspace{23pt} x_{n,2} \hspace{23pt} \cdots \hspace{23pt} x_{n,n} \end{array}$

$\hspace{15pt}$ 第 $n$ 行的字符由一个长度为 $n$ ，只包含 $\texttt{`a'}, \texttt{`b'}, \texttt{`c'}$ 三个字符的字符串决定。
$\hspace{15pt}$ 至于剩下第 $1$ 到 $n-1$ 行的字符 $x$ （不妨记为 $x_{i,j}$ ），均由它左下方 $l$ （记为 $x_{i+1,j}$ ）和右下方 $r$ （记为 $x_{i+1,j+1}$ ）两个字符决定，三个字符 $x,l,r$ 满足条件：
$\hspace{23pt}\bullet\,$ 要么全部相同（例如 $(x,l,r) = (\texttt{`a'}, \texttt{`a'}, \texttt{`a'})$ ）；
$\hspace{23pt}\bullet\,$ 要么全部不同（例如 $(x,l,r) = (\texttt{`a'}, \texttt{`b'}, \texttt{`c'})$ ）。

$\hspace{15pt}$ 显然，这样的倒三角矩阵由第 $n$ 行的 $n$ 个字符唯一确定。
$\hspace{15pt}$ 接下来有 $q$ 个询问，每个询问给你两个整数 $x,y$ ，你需要输出第 $x$ 行的第 $y$ 个字符是什么。

输入描述:

第一行输入两个整数  代表三角矩阵的行数、询问次数。 
第二行输入一个长度为 ，仅由字符  组成的字符串，表示三角矩阵第  行的  个字符。 
此后  行，第  行输入两个整数 ，代表第  次询问。在本题中，没有额外限制。

输出描述:

在一行上输出一个长度为  的字符串 ，第  个字符  表示第  次询问的答案。

示例1

输入

复制

5 3
acbac
3 1
3 2
3 3

输出

复制

cba

说明

在这个样例中，三角形形如下方公式所示：