466. Parking at Secret Object

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A long time ago, in a Galaxy Far Far Away...

Imagine you develop fully automated parking system for Death S... well, secret military object of the Empire. The system manages N parking slots arranged along the equator of the Object and numbered from 1 to N in clockwise direction. Objective of the system is to answer queries of groups of battle dro... let us call them users that from time to time take off and get in to the Object. The only requirement that should be obeyed during processing the inquiries is that every group of users should get some set of unoccupied parking slots adjacent to each other. For example, suppose that the Object has 10 parking slots. If a group of five users calls for permission to get in, you may allot for them, for instance, parking slots from 2 to 6 or 1-2 and 8-10 (remember, parking slots are arranged along the equator of the Object, so they form a circle and slots 1 and N are the neighboring ones).

Let us define a as a maximal (by inclusion) group of unoccupied neighboring slots and the of a cluster as the number of slots in it. Correspondingly, define the of a cluster as the number of the leftmost parking slot in the cluster (the first parking slot when you look over all parking slots of the cluster in clockwise direction), and call this parking slot the of the cluster. If all parking slots in the system are unoccupied, then we treat it as one cluster consisting of all parking slots and having head slot number 1.

To improve efficiency of the parking system you decided to use the following algorithm for determining slots to allot for incoming users. Suppose a group of S users is coming in the land.



  • You choose for them cluster of minimum size not less than S.

  • If there is no such cluster, you reject the query.

  • If there are several such clusters, you choose the one with minimum number.

  • You allot for users S neighboring parking slots starting from head slot of the cluster and going in clockwise direction.



What is left is to implement the logic of the parking system efficiently.

Input
The first line of input file contains two integer numbers N and Q — number of parking slots in the system and number of queries of users (). The second line contains characters 
.
 and 
X
, which represent unoccupied and taken up slots in the system, respectively (starting from the first slot in clockwise direction). i-th character is indicator of whether i-th parking slot in the system occupied or not. The following Q lines contain queries of users. Every line represents i-th query and has one of the two forms:

PARK Si
 — group of Si users wants to land (1 ≤ Si ≤ N).

LEAVE Qi
 — group of users from query Qi wants to take off (1 ≤ Qi < i, queries are numbered from 1 to Q in the order they appear in the input file).

All queries are consistent, so, for example, group of already flown away users cannot query for taking off, or 
LEAVE
 query cannot contain reference to another 
LEAVE
 query.

Output
For every 
PARK
 query in the input file output the only line containing description of set of parking slots allotted for corresponding group of users, or the message 
NO ROOM
 if it is impossible to meet corresponding request.

In case of a positive answer description should be given in the format of ordered intervals precisely as in the examples provided to you below.

Example(s)
sample input
 
sample output
 
10 4
..........
PARK 4
PARK 3
LEAVE 1
PARK 4

1-4
5-7
1,8-10


sample input
 
sample output
 
10 11
....X..X..
PARK 1
PARK 3
PARK 4
LEAVE 2
PARK 5
LEAVE 5
PARK 1
PARK 1
PARK 2
PARK 4
PARK 3

6
1,9-10
NO ROOM
1-3,9-10
7
9
1,10
NO ROOM
2-4