Byteasar 在 Byteburg 经营着一家糖果店。草莓香草味棒棒糖是当地孩子们的最爱。这些棒棒糖由多个长度相同的片段组成，每个片段要么是草莓味，要么是香草味。棒棒糖的价格是其所有片段价值的总和，其中香草味片段价值 1 个拜塔勒（bythaler），草莓味片段价值 2 个拜塔勒。

图 1：一个由五个片段组成的棒棒糖示例，三个草莓味，两个香草味，交替排列。该棒棒糖的价格为 8 个拜塔勒。

目前 Byteasar 只剩下一根棒棒糖了，虽然它可能非常长。作为一名销售员，他很清楚可能没有人会愿意买下整根棒棒糖。因此，他考虑在片段的连接处将棒棒糖折断，以获得更短的棒棒糖。当然，每个待售的片段必须保持完整。

Byteasar 丰富的销售经验以及对儿童心理的了解告诉他，他的小顾客们很可能会想把所有的钱花在一根棒棒糖上。考虑到这一点，他想知道对于哪些 $k$ 值，他手中的棒棒糖可以通过折断，使得其中包含一个价值恰好为 $k$ 个拜塔勒的片段。当然，他也对折断棒棒糖的方法感兴趣。由于这项任务让他感到不知所措，他请求你的帮助。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1\,000\,000$)，中间用空格隔开。它们分别表示店里剩下的最后一根棒棒糖的片段数量，以及需要考虑的 $k$ 值的数量。棒棒糖的片段编号从 $1$ 到 $n$。第二行给出了棒棒糖的 $n$ 个字母描述，由字母 $T$ 和 $W$ 组成，其中 $T$ 表示草莓味片段，$W$ 表示香草味片段；这些字母中的第 $i$ 个指定了第 $i$ 个片段的口味。接下来的 $m$ 行给出了需要考虑的 $k$ 值 ($1 \le k \le 2\,000\,000$)，每行一个。

输出格式

你的程序应输出 $m$ 行，每行对应一个 $k$ 值的查询结果。如果对于给定的 $k$ 值，无法通过折断棒棒糖得到一个价值恰好为 $k$ 个拜塔勒的连续片段，则应输出 NIE（波兰语中的“不”）。否则，输出两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，中间用空格隔开，表示编号从 $l$ 到 $r$（包含 $l$ 和 $r$）的片段组成的棒棒糖价值恰好为 $k$ 个拜塔勒。如果存在多个这样的片段，你的程序可以任意选择其中一个。

样例

输入 1

5 3
TWTWT
5
1
7

输出 1

1 3
2 2
NIE

说明

该样例考虑了图 1 中的棒棒糖。编号从 1 到 3 的片段组成了一个 TWT 棒棒糖，价值为 5 个拜塔勒。编号为 2 的片段是香草味，价值为 1 个拜塔勒。无法从给定的棒棒糖中获得价值为 7 个拜塔勒的片段。