<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
1. Abridged Problem Statement  
You have N parking slots arranged in a circle (numbered 1…N). Some are initially occupied. You must process Q queries of two types:  
• PARK S: allocate S contiguous free slots. You must pick a free cluster whose length ≥ S, choosing the cluster with the smallest length, and if there is a tie, the one with the smallest head index. Allocate the first S slots of that cluster (possibly splitting it) and report the allocated intervals (using wrap‐around across N→1 if needed). If no cluster fits, print “NO ROOM”.  
• LEAVE i: free the slots allocated by the i-th PARK query, merging the freed block with adjacent free clusters on the circle.  

2. Key Observations  
• We need to quickly find the smallest free cluster of size ≥ S and remove or shrink it.  
• We also need to merge freed blocks with neighbors in circular order.  
• Two ordered data structures suffice:  
  – A set (or balanced BST) of free clusters keyed by (size, head) to answer PARK in O(log N).  
  – A set of free clusters keyed by head to find predecessor and successor around the circle in O(log N) for LEAVE.  
• Every cluster is represented by its head position and its size. When you allocate, you remove the old cluster and, if there is leftover space after allocating S, reinsert the remainder at head+S.  
• On LEAVE, you compute the block’s head and total size from stored intervals, locate its immediate neighbors in the head-ordered set, test if they touch the block’s ends (taking wrap-around into account), remove merged clusters, then insert the new merged cluster.

3. Solution Approach  
Maintain:  
• freeBySize = set of tuples (size, head)  
• freeByHead = set of heads  
• A map queryAlloc[i] → list of allocated intervals for the i-th PARK query  
Initialization: scan the initial string of '.' and 'X' to build free clusters (handling wrap-around).  

For each query q = 1…Q:  
  If PARK S:  
    • In freeBySize, find the first cluster with size ≥ S. If none, print “NO ROOM”.  
    • Otherwise, let (cSize, head) be that cluster. Remove it from both sets.  
    • Compute intervals = allocate first S slots from head (one or two intervals if wrapping). Store intervals in queryAlloc[q]. Print them in sorted order, comma-separated.  
    • If cSize > S, reinsert a new cluster at newHead = normalize(head + S) of size (cSize−S).  

  If LEAVE i:  
    • Retrieve intervals = queryAlloc[i]. Remove the entry.  
    • Compute blockHead = intervals[0].first, blockSize = sum over intervals of (r−l+1).  
    • If freeByHead is empty, simply insert (blockHead, blockSize) into both sets.  
    • Otherwise, let endPos = normalize(blockHead + blockSize). In freeByHead, find the first cluster with head ≥ endPos (or wrap to begin) → that is right neighbor; its predecessor in the circular list is left neighbor.  
    • If left’s head+left.size == blockHead (mod N), merge left: remove left, set blockHead = left.head, blockSize += left.size.  
    • If blockHead+blockSize == right.head (mod N), merge right: remove right, blockSize += right.size.  
    • If after merging blockSize == N, set blockHead = 1. Insert the merged cluster (blockSize, blockHead) into both sets.  

Normalization: ensure positions wrap into [1..N].  

4. C++ Implementation with Detailed Comments  
#include <bits/stdc++.h>
using namespace std;

int N, Q;
// Two sets of free clusters:
//   freeBySize: stores (size, head) to pick the smallest fitting cluster
//   freeByHead: stores head to locate neighbors for merging
set<pair<int,int>> freeBySize;
set<int> freeByHead;
// Map head -> size, for removal/lookup
unordered_map<int,int> headToSize;
// Store allocated intervals per PARK query
vector<vector<pair<int,int>>> queryAlloc;

// Normalize p to range [1..N] with wrap-around
int norm(int p) {
    if (p > N) return p - N;
    if (p < 1) return p + N;
    return p;
}
// Given head and len, return 1 or 2 intervals
vector<pair<int,int>> makeIntervals(int head, int len) {
    vector<pair<int,int>> iv;
    if (head + len - 1 <= N) {
        iv.push_back({head, head + len - 1});
    } else {
        iv.push_back({head, N});
        int r = len - (N - head + 1);
        iv.push_back({1, r});
    }
    return iv;
}
// Print intervals as "a-b,c-d,..." or "a"
void printIntervals(const vector<pair<int,int>>& iv) {
    vector<pair<int,int>> tmp = iv;
    sort(tmp.begin(), tmp.end());
    bool first = true;
    for (auto &pr : tmp) {
        if (!first) cout << ",";
        first = false;
        if (pr.first == pr.second)
            cout << pr.first;
        else
            cout << pr.first << "-" << pr.second;
    }
    cout << "\n";
}
// Add a free cluster (head, size)
void addCluster(int head, int size) {
    freeBySize.insert({size, head});
    freeByHead.insert(head);
    headToSize[head] = size;
}
// Remove a free cluster given its head
void removeCluster(int head) {
    int size = headToSize[head];
    freeBySize.erase({size, head});
    freeByHead.erase(head);
    headToSize.erase(head);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;
    string s;
    cin >> s;
    queryAlloc.resize(Q+1);

    // Build initial clusters by scanning from first 'X' or entire circle if none
    int start = -1;
    for (int i = 0; i < N; i++) {
        if (s[i] == 'X') { start = i+1; break; }
    }
    if (start == -1) {
        // All free
        addCluster(1, N);
    } else {
        int i = start;
        do {
            if (s[i-1] == '.') {
                int h = i, len = 0;
                while (s[i-1] == '.') {
                    len++;
                    i = norm(i+1);
                }
                addCluster(h, len);
            } else {
                i = norm(i+1);
            }
        } while (i != start);
    }

    // Process queries
    for (int qi = 1; qi <= Q; qi++) {
        string cmd;
        cin >> cmd;
        if (cmd == "PARK") {
            int S; cin >> S;
            // Find smallest cluster with size >= S
            auto it = freeBySize.lower_bound({S, 0});
            if (it == freeBySize.end()) {
                cout << "NO ROOM\n";
            } else {
                int cSize = it->first;
                int head  = it->second;
                removeCluster(head);
                // Allocate S slots
                auto iv = makeIntervals(head, S);
                queryAlloc[qi] = iv;
                printIntervals(iv);
                // Remainder
                if (cSize > S) {
                    int newHead = norm(head + S);
                    addCluster(newHead, cSize - S);
                }
            }
        } else {
            // LEAVE i
            int iref; cin >> iref;
            auto iv = queryAlloc[iref];
            // Compute block head and size
            int head = iv[0].first;
            int len = 0;
            for (auto &pr: iv) len += pr.second - pr.first + 1;
            // If no free clusters, just insert
            if (freeByHead.empty()) {
                addCluster(head, len);
                continue;
            }
            // Find right neighbor: first head >= endPos, or wrap
            int endPos = norm(head + len);
            auto itR = freeByHead.lower_bound(endPos);
            if (itR == freeByHead.end()) itR = freeByHead.begin();
            // Left neighbor is predecessor in circular order
            auto itL = (itR == freeByHead.begin())
                       ? prev(freeByHead.end())
                       : prev(itR);
            // Merge tests
            bool mergeL = norm(*itL + headToSize[*itL]) == head;
            bool mergeR = norm(head + len) == *itR;
            if (mergeL) {
                int lh = *itL, ls = headToSize[lh];
                removeCluster(lh);
                head = lh;
                len += ls;
            }
            if (mergeR) {
                int rh = *itR, rs = headToSize[rh];
                removeCluster(rh);
                len += rs;
            }
            if (len == N) head = 1;
            addCluster(head, len);
        }
    }
    return 0;
}

5. Python Implementation with Detailed Comments  
import sys, bisect

def norm(p, N):
    # Wrap p into [1..N]
    if p > N: return p - N
    if p < 1: return p + N
    return p

def makeIntervals(head, length, N):
    # Return 1 or 2 intervals for a block starting at head
    if head + length - 1 <= N:
        return [(head, head + length - 1)]
    else:
        first = (head, N)
        rem = length - (N - head + 1)
        second = (1, rem)
        return [first, second]

def formatIntervals(iv):
    iv_sorted = sorted(iv)
    parts = []
    for l, r in iv_sorted:
        if l == r:
            parts.append(str(l))
        else:
            parts.append(f"{l}-{r}")
    return ",".join(parts)

data = sys.stdin.read().split()
it = iter(data)
N, Q = int(next(it)), int(next(it))
slots = next(it).strip()

# Two sorted lists of free clusters:
#   bySize: list of (size, head)
#   byHead: list of heads
bySize = []
byHead = []
headToSize = dict()
queryAlloc = dict()

# Functions to add/remove clusters
def addCluster(head, size):
    bisect.insort(bySize, (size, head))
    bisect.insort(byHead, head)
    headToSize[head] = size

def removeCluster(head):
    size = headToSize[head]
    i = bisect.bisect_left(bySize, (size, head))
    bySize.pop(i)
    j = bisect.bisect_left(byHead, head)
    byHead.pop(j)
    del headToSize[head]

# Build initial free clusters
firstX = next((i+1 for i,ch in enumerate(slots) if ch=='X'), None)
if firstX is None:
    addCluster(1, N)
else:
    i = firstX
    while True:
        if slots[i-1] == '.':
            h, length = i, 0
            while slots[i-1] == '.':
                length += 1
                i = norm(i+1, N)
            addCluster(h, length)
        else:
            i = norm(i+1, N)
        if i == firstX:
            break

out = []
for qi in range(1, Q+1):
    typ = next(it)
    if typ == 'PARK':
        S = int(next(it))
        # find first cluster with size >= S
        idx = bisect.bisect_left(bySize, (S, 0))
        if idx == len(bySize):
            out.append("NO ROOM")
        else:
            size, head = bySize[idx]
            removeCluster(head)
            iv = makeIntervals(head, S, N)
            queryAlloc[qi] = iv
            out.append(formatIntervals(iv))
            # leftover
            if size > S:
                newHead = norm(head + S, N)
                addCluster(newHead, size - S)
    else:
        # LEAVE iref
        iref = int(next(it))
        iv = queryAlloc.pop(iref)
        # compute head and length
        head = iv[0][0]
        length = sum(r - l + 1 for l,r in iv)
        if not byHead:
            addCluster(head, length)
        else:
            endPos = norm(head + length, N)
            # right neighbor
            j = bisect.bisect_left(byHead, endPos)
            if j == len(byHead):
                j = 0
            # left neighbor
            k = j-1 if j > 0 else len(byHead)-1
            lh = byHead[k]; ls = headToSize[lh]
            rh = byHead[j]; rs = headToSize[rh]
            mergeL = norm(lh + ls, N) == head
            mergeR = norm(head + length, N) == rh
            if mergeL:
                removeCluster(lh)
                head = lh
                length += ls
            if mergeR:
                removeCluster(rh)
                length += rs
            if length == N:
                head = 1
            addCluster(head, length)

print("\n".join(out))