259 - Software Allocation

學校的計算機中心有十台電腦(以0~9作編號)，所有電腦只支援單一行程。電腦上共有26個應用程式可供執行(分別以A~Z表示)，下面會說明哪些電腦可以執行哪些應用程式。

每天早上，使用者會帶著他們當天需要執行的應用程式到計算機中心，可能會有兩位使用者帶相同的應用程式，但此時就需要兩台不同的電腦分別執行該程式。

計算機中心的櫃台會收集當天所有使用者的應用程式，並整理一份各個應用程式能在哪幾台電腦執行的清單，並將每個應用程式指派給電腦去執行，注意，每台電腦一天只能執行一個應用程式。

櫃台所整理的清單格式如下：

1. 一個大寫的字元A...Z表示一種應用程式。
2. 一個位數的數字1...9表示該應用程式有幾位使用者需要執行。
3. 一個空白字元。
4. 一或多個位數的數字0~9表示該應用程式可在哪些電腦上執行。
5. 一個表示該列結束的分號 ;。
6. 換程符號。
   

Input

輸入會有多組測試資料，每組資料以一列空行隔開，且會有一到多列清單資訊，請你寫程式判斷該組資料是否有足夠的電腦來執行，如果足夠的話，請輸出一組可能的配置方式。

Output

每組測試資料輸出一列，其格式如下：

• 若存在一組可能的配置方式，請輸出十個{'A'...'Z', '_'}的字元，分別依序表示這十台電腦上分別執行哪個應用程式，以 _ 表示該台電腦並不需要執行任何應用程式。
• 一個 ! 字元表示找不到任何一種可能的配置方式來執行所有應用程式。
  

Sample Input

A4 01234;
Q1 5;
P4 56789;

A4 01234;
Q1 5;
P5 56789;

Sample Output

AAAA_QPPPP
!

原文出處