Lollipop

Byteasar runs a confectionery in Byteburg. Strawberry and vanilla lollipops are the favourite treat of the local children. Each lollipop is made of several segments of equal length, and every segment is either strawberry or vanilla flavoured. The price of a lollipop is the sum of the prices of its segments: a vanilla segment costs one bythaler, and a strawberry segment costs two.

Fig. 1: An example lollipop of five segments, three strawberry and two vanilla, placed alternately. The price of this lollipop is 8 bythalers.

Byteasar now has only a single lollipop left, though it may be very long. Knowing that nobody will buy the whole thing, he wants to break it at the joints between segments to obtain shorter lollipops. Every piece he sells must stay in one connected part.

His young customers usually want to spend all of their money on one lollipop. So for a given value k, Byteasar wonders whether he can break the lollipop so that one of the resulting connected pieces is worth exactly k bythalers, and if so, how to cut it. Answer this for several values of k.

The first line contains two integers n and m (1 ≤ n, m ≤ 1,000,000), separated by a single space: the number of segments of the remaining lollipop and the number of values of k to consider. The segments are numbered from 1 to n. The second line contains a string of length n describing the lollipop, made up of the letters T and W only. T marks a strawberry segment and W a vanilla segment; the i-th letter gives the flavour of the i-th segment. Each of the next m lines contains one value of k to consider (1 ≤ k ≤ 2,000,000).

Print exactly m lines, one result per value of k in order. If it is impossible to obtain a connected fragment worth exactly k bythalers, print NIE. Otherwise print two integers l and r separated by a single space (1 ≤ l ≤ r ≤ n), meaning that the fragment consisting of segments l through r is worth exactly k bythalers. If several pairs (l, r) satisfy this, print the lexicographically smallest one: the smallest l, and among those the smallest r.