#2156. 「POI2011 R1」棒棒糖 Lollipop

内存限制:256 MiB 时间限制:600 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: ceba_robot

题目描述

译自 POI 2011 Round 1. B「Lollipop

Byteasar 在比特镇开了一家糖果店,草莓香草味的棒棒糖是当地孩子们的最爱。这些棒棒糖都是由长度相同的香草味或者草莓味的片段组成的。一整根棒棒糖的价格是每一段棒棒糖的价格之和,每一段香草味的棒棒糖价格为一元,草莓味的棒棒糖价格为两元。

图1:举个例子,这是一根由五段组成的棒棒糖,草莓味和香草味的棒棒糖交替排列,这根棒棒糖的价格为 8 元。

现在,Byteasar 只剩下最后一根棒棒糖了。这根棒棒糖太长了,因此 Byteasar 认为绝对没有人会买下这一整根。所以,他想要把这一整根在接缝处掰成几段,每一段单独出售。

Byteasar 的人生经验告诉他,他的顾客希望把自己的钱花在单独的一根棒棒糖上,于是他想知道这一根棒棒糖有没有连续的一段的价格是 k 。但这个问题对他来说太难了,他希望你能帮帮他。

输入格式

输入的第一行包含两个整数 n, m ,分别表示最后仅存的这根棒棒糖的长度和要考虑的价格的数量(询问的数量)。棒棒糖的每一段从 1 n 编号。
第二行包含一个由WT组成的字符串,描述了最后仅存的这根棒棒糖,其中第 i 个字母描述第 i 段的口味,T表示草莓片段(价格为 2 元),W表示香草片段(价格为 1 元)。
接下来的 m 行每行包含一个整数 k_i ,表示第 i 个要考虑的连续片段的价格。

输出格式

你应当输出 m 行,第 i 行表示第 i 个询问的结果。如果在这根棒棒糖中没有连续的一段的价格为 k_i ,应输出NIE(波兰语中的No),否则应输出两个整数 l r ,表示最后仅存的这根棒棒糖从 l r 的片段价格为 k_i 。若有多个可能的答案,输出一个即可,评测系统会使用 Special Judge 判断你的输出是否正确。

样例

样例输入

5 3
TWTWT
5
1
7

样例输出

1 3
2 2
NIE

样例解释

这个例子与图1相同,从 1 3 的片段组成了TWT的棒棒糖,价格为 5 。第 2 段棒棒糖是香草味的,价格为 1 。并没有办法得到一个价值为 7 的棒棒糖。

数据范围与提示

对于 100\% 的数据, 1 \le n, m \le 1000000 , 1 \le k \le 2000000

Task author: Jakub Pachocki.
翻译和 SPJ: ceba