옷 보관하기

어느 세탁소에서는 옷을 옷걸이에 걸어, 컴퓨터가 전기로 회전시키는 원형 레일에 고정된 고리(hook)에 보관한다. 고리에는 번호가 매겨져 있어 어떤 옷이든 쉽게 찾을 수 있으며, 레일은 원하는 고리가 고정된 표시(mark) 앞으로 오도록 돌아간다.

레일을 크기 $N$인 원형 배열로 보고, 인덱스는 $N$으로 나눈 나머지로 생각한다. 옷 $n$벌을 한 묶음으로 맡기려면 작업자가 $n$을 입력한다. 컴퓨터는 지금 표시 앞에 있는 고리에서 시작해 오른쪽(인덱스가 커지는 방향, $N$에 대한 나머지)으로 훑으면서, 사용할 수 있는 고리 $n+2$개가 연속된 첫 구간 $k, k+1, \dots, k+n+1$을 찾는다. 이때 고리 $k$와 고리 $k+n+1$은 칸막이(separator)가 되어 옷을 걸지 않으며, 옷 $n$벌은 고리 $k+1, \dots, k+n$에 건다. 그 뒤 레일은 고리 $k+n+1$이 표시 앞에 오도록 돌아가고, 작업자는 손님에게 번호표 $k$를 준다. 손님의 옷이 걸린 고리는 세탁하는 동안에도 그 손님에게 배정된 채로 남는다.

칸막이는 공유될 수 있다. 즉 구간의 양 끝 고리는 이미 칸막이인 고리를 다시 사용해도 된다. 다만 가운데 $n$개의 고리는 반드시 비어 있어야 한다.

손님이 번호표 $k$를 들고 돌아오면 작업자는 $k$를 입력한다. 그러면 그 묶음의 칸막이 고리 $k$가 표시 앞에 오도록 레일이 돌아간다(옷을 돌려주는 동안 레일은 움직이지 않는다). 그 묶음의 옷이 걸려 있던 모든 고리는 비게 된다. 또한 없어진 묶음의 칸막이 고리도, 그 양옆 이웃이 모두 비어 있으면 함께 비게 된다. (칸막이 고리는 양옆 이웃이 모두 비는 순간 어떤 용도로든 다시 쓸 수 있다.)

처음에는 레일이 비어 있고 고리 $0$이 표시 앞에 있다. 맡긴 적이 있는 옷만 찾아갈 수 있다.

첫째 줄에 고리의 개수 $N$이 주어진다 ($1 \le N \le 300$). 둘째 줄에 뒤따르는 명령의 개수 $l$이 주어진다. 다음 $l$개의 줄은 각각 다음 두 형식 중 하나이다.

D n

옷 $n$벌을 맡긴다. 또는

W k

번호표 $k$인 묶음을 찾아간다 ($0 \le k < N$).

각 명령에 대해 해당하는 메시지를 출력한다.

맡기는 명령에서 조건을 만족하는 고리 $n+2$개의 연속 구간이 없으면 다음을 출력한다.

No space left, please come back later.

번호표 $k$가 발급되면 다음을 출력한다.

The launderer gives ticket k.

번호표 $k$인 묶음을 찾아가면 다음을 출력하고,

The launderer gives back batch k.

그 묶음의 고리를 모두 비운다. 고리 $h, \dots, h+q$가 비게 될 때마다(인덱스는 $N$에 대한 나머지로, 연속된 구간이다) $h$부터 $h+q$까지 순서대로 다음을 출력한다.

i is freed.