Problem : 88 - Lollipop

Special Judge

Problem Statistics

Solved Member: 26　　Submission: 96　　User Tried: 27

Statement:

「等哥這次掙錢，咱買棒棒糖，

　　　買兩根，一根你看著我吃，另一根我吃給你看。」

　　　　　　　　　　　　　　by 爾康

棒棒糖，一根長長的棒棒糖，有著兩種口味穿插長長的棒棒糖。

兩種口味，草莓與香草！每塊草莓1元香草2元，當有客人找炉裏買棒棒糖時，大概都會傾家蕩產的把錢都給炉裏！為了維護商譽，炉裏是不會讓客人受委屈的！但炉裏家中也頗清寒，所以也不能吃虧，當客人給炉裏K元時，不知道炉裏是否能找到一段連續且適合的棒棒糖，剪下來送給客人呢？

這個問題困擾炉裏很久了，不知你能不能幫他解決？

Input:Output:

第一行有兩個整數n m (1 ≤ n, m ≤ 1000000)，分別代表棒棒糖的長度與詢問數。
第二行有長度為n塊，以W(草莓)與T(香草)組成的棒棒糖。
接下來有m行，每行一個整數K(1 ≤ K ≤ 2000000)。

對於每一個K，請輸出兩個數字L R(1 ≤ L ≤ R ≤ 1000000)，代表"從左算起第L塊"到"從左算起第R塊"的價值剛好為K元，若有多組解可以輸出任意一組，若找不到請輸出"NIE"(不含雙引號)。

Sample Input:Sample Output:

5 3
TWTWT
5
1
7

1 3
2 2
NIE

HINT:

其實炉裏就是某条。

對於SAMPLE A:
我們回傳1 3，代表從棒棒糖的第1塊到第3塊"TWT"，價格為2+1+2=5，正好為客人所求。

Source:

POI 18 Stage 1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-ocen	1000ms	65536kb
1-1	1000ms	65536kb	7
1-2	1000ms	65536kb
1-3	1000ms	65536kb
2-ocen	1000ms	65536kb
2-1	1000ms	65536kb	7
2-2	1000ms	65536kb
2-3	1000ms	65536kb
3-ocen	1000ms	65536kb
3-1	1000ms	65536kb	7
3-2	1000ms	65536kb
3-3	1000ms	65536kb
4-ocen	5000ms	65536kb
4-1	1000ms	65536kb	8
4-2	1000ms	65536kb
4-3	1000ms	65536kb
5-1	1000ms	65536kb	8
5-2	1000ms	65536kb
5-3	1000ms	65536kb
6-1	1500ms	65536kb	8
6-2	1500ms	65536kb
6-3	1500ms	65536kb
7-1	1500ms	65536kb	9
7-2	1500ms	65536kb
7-3	1500ms	65536kb
8-1	3000ms	65536kb	9
8-2	3000ms	65536kb
8-3	3000ms	65536kb
9-1	4500ms	65536kb	9
9-2	4500ms	65536kb
9-3	4500ms	65536kb
10-1	4500ms	65536kb	9
10-2	4500ms	65536kb
10-3	4500ms	65536kb
11-1	5000ms	65536kb	9
11-2	5000ms	65536kb
11-3	5000ms	65536kb
12-1	5000ms	65536kb	10
12-2	5000ms	65536kb
12-3	5000ms	65536kb