막대사탕

바이트버그에서 바이테아사르가 과자 가게를 운영한다. 딸기와 바닐라 맛이 섞인 막대사탕은 동네 아이들이 가장 좋아하는 간식이다. 이 막대사탕은 길이가 같은 여러 조각으로 이루어지며, 각 조각은 딸기 맛이거나 바닐라 맛이다. 막대사탕의 가격은 모든 조각 가격의 합이고, 바닐라 조각은 1 바이탈러, 딸기 조각은 2 바이탈러이다.

그림 1: 조각 다섯 개로 이루어진 막대사탕의 예. 딸기 맛 세 개와 바닐라 맛 두 개가 번갈아 놓여 있다. 이 막대사탕의 가격은 8 바이탈러이다.

지금 바이테아사르에게는 (아주 길 수도 있는) 막대사탕 하나만 남아 있다. 통째로는 아무도 사지 않을 것을 알기에, 그는 조각의 이음매를 끊어 더 짧은 막대사탕으로 나누려 한다. 팔려는 각 조각은 반드시 이어진 한 덩어리여야 한다.

아이들은 대개 가진 돈을 막대사탕 하나에 모두 쓰고 싶어 한다. 그래서 바이테아사르는 어떤 값 k에 대해, 막대사탕을 잘라서 정확히 k 바이탈러짜리 이어진 조각을 하나 얻을 수 있는지, 그리고 그렇다면 어떻게 자르면 되는지 궁금하다. 여러 개의 k 값에 대해 답하여라.

첫 번째 줄에 두 정수 n과 m이 공백 하나로 구분되어 주어진다 (1 ≤ n, m ≤ 1,000,000). 각각 남은 막대사탕의 조각 수와 확인할 k 값의 개수를 뜻한다. 조각은 1번부터 n번까지 번호가 매겨진다. 두 번째 줄에는 막대사탕을 나타내는 길이 n의 문자열이 주어지며, 문자 T와 W로만 이루어진다. T는 딸기 맛, W는 바닐라 맛 조각을 뜻하고, i번째 문자가 i번 조각의 맛을 나타낸다. 이어지는 m개의 줄에는 확인할 k 값이 한 줄에 하나씩 주어진다 (1 ≤ k ≤ 2,000,000).

각 k 값에 대해 한 줄씩, 모두 m개의 줄을 출력한다. 정확히 k 바이탈러짜리 이어진 조각을 만들 수 없으면 NIE를 출력한다. 만들 수 있으면 두 정수 l과 r을 공백 하나로 구분하여 출력한다 (1 ≤ l ≤ r ≤ n). 이는 l번부터 r번까지의 조각으로 이루어진 부분이 정확히 k 바이탈러임을 뜻한다. 조건을 만족하는 (l, r)이 여러 개이면 사전순으로 가장 앞서는 것, 즉 l이 가장 작고 그중 r이 가장 작은 것을 출력한다.