<|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 of free clusters keyed by (size, head, id) to answer PARK in O(log N).
  - A set of free clusters keyed by (head, id) 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:
• clusters_by_size = set of tuples (size, head, id)
• clusters_by_pos = set of pairs (head, id)
• cluster_info: map id → (head, size)
• cluster_head_to_id: map head → id
• query_allocations: map query index → list of allocated intervals
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 clusters_by_size, find the first cluster with size ≥ S. If none, print "NO ROOM".
    • Otherwise, let (cSize, head, id) 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 query_allocations[q]. Print them sorted, comma-separated.
    • If cSize > S, reinsert a new cluster at newHead = normalize(head + S) of size (cSize−S).

  If LEAVE i:
    • Retrieve intervals = query_allocations[i]. Remove the entry.
    • Compute blockHead = intervals[0].first, blockSize = sum over intervals of (r−l+1).
    • If clusters_by_pos is empty, simply insert (blockHead, blockSize) into both sets.
    • Otherwise, let endPos = normalize(blockHead + blockSize). In clusters_by_pos, 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.

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

4. C++ Implementation with Detailed Comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int N, Q;
string slots;

set<tuple<int, int, int>> clusters_by_size;
set<pair<int, int>> clusters_by_pos;
map<int, int> cluster_head_to_id;
map<int, pair<int, int>> cluster_info;
map<int, vector<pair<int, int>>> query_allocations;
int next_cluster_id = 0;

void add_cluster(int head, int size) {
    int id = next_cluster_id++;
    clusters_by_size.insert({size, head, size});
    clusters_by_pos.insert({head, id});
    cluster_head_to_id[head] = id;
    cluster_info[id] = {head, size};
}

void remove_cluster(int id) {
    auto [head, size] = cluster_info[id];
    clusters_by_size.erase({size, head, size});
    clusters_by_pos.erase({head, id});
    cluster_info.erase(id);
}

int normalize(int pos) {
    if(pos <= 0) {
        return pos + N;
    }
    if(pos > N) {
        return pos - N;
    }
    return pos;
}

vector<pair<int, int>> get_intervals(int head, int size) {
    vector<pair<int, int>> intervals;
    if(head + size - 1 <= N) {
        intervals.push_back({head, head + size - 1});
    } else {
        intervals.push_back({head, N});
        intervals.push_back({1, size - (N - head + 1)});
    }
    return intervals;
}

void print_intervals(vector<pair<int, int>>& intervals) {
    sort(intervals.begin(), intervals.end());

    bool first = true;
    for(auto [l, r]: intervals) {
        if(!first) {
            cout << ",";
        }
        first = false;
        if(l == r) {
            cout << l;
        } else {
            cout << l << "-" << r;
        }
    }
    cout << "\n";
}

void read() {
    cin >> N >> Q;
    cin >> slots;
}

void solve() {
    /*
       We can do everything with std::set / binary search trees. We maintain two
       ways of accessing the clusters - one based on their lengths, and another
       based on their number / left location. Then searching for the correct
       cluster can be done with lower bound, and with some casework we can
       update what happens to the adjacent clusters (on addition and removal).
       We have to be extra careful about the wrapping.
    */

    int blocked = -1;
    for(int i = 1; i <= N; i++) {
        if(slots[i - 1] == 'X') {
            blocked = i;
            break;
        }
    }

    if(blocked == -1) {
        add_cluster(1, N);
    } else {
        int i = blocked;
        do {
            if(slots[i - 1] == '.') {
                int head = i;
                int size = 0;
                while(slots[i - 1] == '.') {
                    size++;
                    i = normalize(i + 1);
                }
                add_cluster(head, size);
            } else {
                i = normalize(i + 1);
            }
        } while(i != blocked);
    }

    for(int q = 1; q <= Q; q++) {
        string type;
        cin >> type;

        if(type == "PARK") {
            int S;
            cin >> S;

            auto it = clusters_by_size.lower_bound({S, -1, -1});
            if(it == clusters_by_size.end()) {
                cout << "NO ROOM\n";
            } else {
                auto [size, head, _] = *it;
                int cluster_id = cluster_head_to_id[head];

                vector<pair<int, int>> allocated = get_intervals(head, S);
                query_allocations[q] = allocated;
                print_intervals(allocated);

                remove_cluster(cluster_id);

                if(size > S) {
                    int new_head = normalize(head + S);
                    add_cluster(new_head, size - S);
                }
            }
        } else {
            int qi;
            cin >> qi;

            auto _tmp_q_it = query_allocations.find(qi);
            assert(_tmp_q_it != query_allocations.end());

            vector<pair<int, int>> intervals = _tmp_q_it->second;
            query_allocations.erase(_tmp_q_it);

            int head = intervals[0].first;
            int size = 0;
            for(auto [l, r]: intervals) {
                size += (r - l + 1);
            }

            if(clusters_by_pos.empty()) {
                add_cluster(head, size);
                continue;
            }

            auto cw_it =
                clusters_by_pos.lower_bound({normalize(head + size), -1});

            auto ccw_it = prev(
                cw_it != clusters_by_pos.begin() ? cw_it : clusters_by_pos.end()
            );

            if(cw_it == clusters_by_pos.end()) {
                cw_it = clusters_by_pos.begin();
            }

            int l_id = ccw_it->second, r_id = cw_it->second;

            bool merge_left =
                normalize(
                    cluster_info[l_id].first + cluster_info[l_id].second
                ) == head;
            bool merge_right =
                normalize(head + size) == cluster_info[r_id].first;

            if(merge_left) {
                head = cluster_info[l_id].first;
                size += cluster_info[l_id].second;
                remove_cluster(l_id);
            }

            if(merge_right) {
                size += cluster_info[r_id].second;
                remove_cluster(r_id);
            }

            if(size == N) {
                head = 1;
            }
            add_cluster(head, size);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }
    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys, bisect

def normalize(pos, N):
    """Wrap pos into [1..N]."""
    if pos > N: return pos - N
    if pos < 1: return pos + N
    return pos

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):
    """Format intervals as 'a-b,c-d,...' or single numbers."""
    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, id)
#   byHead: list of (head, id)
bySize = []
byHead = []
headToSize = dict()
queryAlloc = dict()
next_cid = 0

def addCluster(head, size):
    global next_cid
    cid = next_cid
    next_cid += 1
    bisect.insort(bySize, (size, head, cid))
    bisect.insort(byHead, (head, cid))
    headToSize[head] = size

def removeCluster(head):
    size = headToSize[head]
    cid = headToSize.get(head, None)
    # Find by binary search
    i = bisect.bisect_left(bySize, (size, head, 0))
    while i < len(bySize) and bySize[i][:2] == (size, head):
        bySize.pop(i)
        break
    j = bisect.bisect_left(byHead, (head, 0))
    while j < len(byHead) and byHead[j][0] == head:
        byHead.pop(j)
        break
    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 = normalize(i+1, N)
            addCluster(h, length)
        else:
            i = normalize(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, -1, -1))
        if idx == len(bySize):
            out.append("NO ROOM")
        else:
            size, head, cid = bySize[idx]
            removeCluster(head)
            iv = makeIntervals(head, S, N)
            queryAlloc[qi] = iv
            out.append(formatIntervals(iv))
            if size > S:
                newHead = normalize(head + S, N)
                addCluster(newHead, size - S)
    else:
        # LEAVE iref
        iref = int(next(it))
        iv = queryAlloc.pop(iref)
        head = iv[0][0]
        length = sum(r - l + 1 for l,r in iv)
        if not byHead:
            addCluster(head, length)
        else:
            endPos = normalize(head + length, N)
            # right neighbor
            j = bisect.bisect_left(byHead, (endPos, -1))
            if j == len(byHead):
                j = 0
            # left neighbor
            k = j-1 if j > 0 else len(byHead)-1
            lh = byHead[k][0]; ls = headToSize[lh]
            rh = byHead[j][0]; rs = headToSize[rh]
            mergeL = normalize(lh + ls, N) == head
            mergeR = normalize(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))
```
