[IOI Camp Judge 48]Kokokko (題目備份)

IOI Camp Judge是暫時性的，因此在此作題目備份
題解在這裡，請參考~

Kokokko

Time Limit: 5s

Description

HH 自從上次玩切蛋糕遊戲輸給 YY，被迫吃下壓克力蛋糕後，牙齒已經斷了一大半，剩下的也大多鬆脫，走路不時會發出 “Ko Ko Ko” 的聲音。慘到如此地步的 HH 自然無法接受，於是他花了整整三年的時間研發了一種稱為「巧－壓轉換壹字自動機」（Cho-Acr Transformation One-Word Auto-Machine）的機器，可以利用壓克力分子的共振特性，把壓克力蛋糕轉換成巧克力蛋糕，以避免壓克力蛋糕再度危害到他僅剩不多的牙齒。

有一次 HH 生日時，YY 送了一個矩形的 N×M 巧克力蛋糕給他，結果一打開，裡面居然夾雜了一堆壓克力，NM 塊蛋糕中只有 K 塊是巧克力！HH 馬上發覺不妙，立刻把他的巧－壓轉換壹字自動機拿出來。為了復仇，他決定乾脆拿這塊蛋糕跟 YY 對決！

蛋糕是一個 N×M 的矩形，每一格初始型態有可能是巧克力或壓克力。(1,1) 為左上角，(N,M) 為右下角。由 YY 先開始，兩人輪流使用巧－壓轉換壹字自動機。巧－壓轉換壹字自動機的使用方式有點複雜，每次必須在蛋糕上選擇一塊矩形區域，並且區域的最右下角必須是 巧克力。接著巧－壓轉換壹字自動機會把位在矩形區域角落的格子（可能有一個、兩個或四個）轉換型態（巧克力變壓克力，壓克力變巧克力）。如果輪到某人時蛋糕已經全部被轉換成壓克力，則該個可憐人就必須把整個壓克力蛋糕吃下肚。

眼看著 HH 就要再度吃下壓克力了，但聰明的你決定趁 YY 去上廁所的空檔，把蛋糕的相對位置重新排列，希望能讓 HH 有機會獲勝。究竟有沒有辦法辦到呢？

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。每筆測試資料第一行有三個整數 N,M,K，代表蛋糕的長寬，以及其中巧克力的塊數。

• 1≤T≤200
• 1≤N,M≤20
• 0≤K≤N×M

Output Format

對於每筆測試資料，請輸出一行一個字串。如果你能夠幫助 HH 獲得勝利，請輸出 “^v^;;”；如果他命中注定必須再度啃壓克力，請輸出 “ko_ko_ko”。

如果 HH 能獲得勝利，你必需再輸出 N 行每行 M 個字元，代表重排列後蛋糕的形式。第 i 行第 j 字元代表 (i,j) 位置蛋糕的形態，‘C’ 代表巧克力（Chocolate），‘A’ 代表壓克力（Acrylic）。輸出必須恰好包含 K 個 ‘C’。

Sample Input

3
3 2 3
3 1 1
4 4 4

Sample Output

^v^;;
AA
CA
CC
ko_ko_ko
^v^;;
AAAA
AAAA
AACA
ACCC