TopCoder

User's AC Ratio

86.7% (13/15)

Submission's AC Ratio

28.0% (14/50)

Tags

Description

今天是弁天堂新型遊戲機owee發售的日子,為了比誰都更早獲得新型遊戲機owee,在聖地.秋葉原已經展開了熱血OTAKU們的聖戰。

圖一:owee

這台新型遊戲機最大的賣點是「虛擬控制」,當玩家穿起防風鏡、手套、靴子一整套裝備,就能夠享受身歷其境的遊戲體驗。

現在OTAKU們為了購買owee,他們即將前往各個店家排隊購買。在江戶.秋葉原中,目前有 $N$ 個店家有販售owee,OTAKU們會選擇各個不同的店家去排隊購買,各個OTAKU可能會前往不同的店家排隊,當一位OTAKU買到owee後就會離開隊伍。當一個店家的owee暫且銷售一空之後,為了能夠盡早獲得owee,排在該隊伍的最前方的OTAKU會帶著整個隊伍前往看起來可能可以買到owee的店家。

現在,在三年前就已經開始排隊武藏大叔已經記錄下了到目前所有的排隊情況。

圖二:武藏大叔與MADAO的作品海報。

在武藏大叔的紀錄中,依序有$M$個紀錄。每個紀錄會有下列三種形式:

  • ADD i id : 代表編號為 $id$ 的OTAKU前往店家 $i$ ,排在隊伍的最後端。
  • LEAVE i : 代表店家 $i$ 賣出了一台owee給排在店家 $i$ 隊伍最前端的OTAKU,這位OTAKU會離開這個隊伍。
  • JOIN i j : 店家 $i$ 的目前有的owee已銷售一空,不知道何時才會補貨。所以原本排在店家 $i$ 的隊伍一同前往店家 $j$ ,依原本順序排在店家 $j$ 隊伍的最後端。

無意間獲得這份紀錄的MADAO,想要知道現在所有店家隊伍的排隊情況,想請你能夠寫一個程式幫助他。

Input Format

輸入的第一行包含兩個整數$N,M$ $(N\leq 100, M \leq 1,000,000)$,店家的編號為$1\sim N$,代表秋葉原上一共有 $N$ 個店家,以及接下來有 $M$ 筆紀錄。接下來的 $M$ 行代表了這 $M$ 筆紀錄,格式與意義請參照上述的題目說明,OTAKU的編號範圍為$1\sim 10^6$。

輸入的測試資料中保證一個編號為 $i$ 的OTAKU不會同時出現在不同隊伍中。

Output Format

若遇到紀錄為"LEAVE i",但是實際上當時店家 $i$ 並沒有人在排隊時,代表武藏大叔記錄錯了,請輸出一行"queue i is empty!"( $i$ 為實際上店家之編號,輸出不包含雙引號,記得換行。),如果不是如同前面所敘述的狀況,對於其他紀錄不需要輸出任何文字。

在你的程式處理完所有紀錄之後,請輸出 $N$ 行代表各個店家目前排隊的情況。第 $i$ 行輸出第 $i$ 個店家的排隊情形,若當前隊伍已經是空的,請輸出一行"queue i: empty"( $i$ 為該店家編號);若隊伍中還有OTAKU的話,請輸出一行"queue i: id[1] id[2] id[3] ..."( id[1] 代表排在隊伍最前端OTAKU的編號,id[2]為第二位,依序下去。行末請勿輸出多餘空白。),若有不清楚的地方詳見範例輸出。

Sample Input 1

3 10
ADD 1 1
ADD 1 2
ADD 2 3
ADD 2 4
ADD 3 5
LEAVE 3
LEAVE 3
ADD 3 6
JOIN 2 3
JOIN 1 2

Sample Output 1

queue 3 is empty!
queue 1: empty
queue 2: 1 2
queue 3: 6 3 4

Hints

Problem Source

NEOJ Problem 25

Subtasks

No. Testdata Range Constraints Score
1 0 $M \leq 1000$ 20
2 1~2 上述子題的條件不再成立。 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 2