题目描述

给一个只有 $1$ 和 $2$ 的序列，每次询问有没有一个子串的和为 $x$。

输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 10 ^ 6$）。

第二行一个长为 $n$ 的只含 $\texttt T$ 和 $\texttt W$ 的字符串，$\texttt T$ 代表 $2$，$\texttt W$ 代表 $1$。

接下来 $m$ 行，每行一个整数 $x$（$1 \le x \le 2\times 10 ^ 6$）表示一次询问。

输出格式

$m$ 行，如果有解则输出两个整数 $l, r$ 表示区间 $[l, r]$ 的和是 $x$，如果无解则输出字符串 NIE。

5 3
TWTWT
5
1
7

1 3
2 2
NIE