殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式，而現在要講的，是殿壬九個月大的時候所思考的一個問題。
小時候（一個月大的時候），殿壬總是計算一串數字當中有幾個「洞」來練習數數。現在
（九個月大），殿壬把這項目標轉移到了小寫英文字⺟上面。
所謂的「洞」，指的是把一串小寫英文字⺟用指定的字體寫下來之後，會有幾個區域被字⺟ 圍住。
殿壬所使用的字體如下（以 pdf 版為準）： abcdefghijklmnopqrstuvwxyz
可以看出a、b、d、e、o、p、q這 7 個英文字⺟有 1 個洞，而g這個英文字⺟有 2 個洞，其餘的 18 個英文字⺟都沒有洞。
對於一個由小寫英文字⺟組成的字串，只要把每個字⺟有幾個洞相加起來，就可以得到整個字串有幾個洞了。舉例來說，abc有 2 個洞，而ppap有 4 個洞。
現在，殿壬想要把所有⻑度為 N 且恰有 K 個洞的小寫英文字串找出來；不過，殿壬非常討厭g這個英文字⺟（原因不明），所以所有包含字⺟g的字串都不會被列入。
殿壬會把滿足上述條件的字串通通列出來並且按照字典順序排序。所謂的字典順序，就是從第一個字⺟開始比較兩個字串，若兩個字串的第一個字⺟不同，那麼第一個字⺟比較小的字串字典順序就比較小；若兩個字串的第一個字⺟相同，那麼就接續比較第二個字⺟、第三個字
⺟等，直到兩個字串在該字⺟相異而比較出字典順序為止。
舉例來說，當 N 為 5、K 為 2 時，滿足條件的字串就有bdyiu、xyzaa、abyss等，按照字典順序排序之後，會依序得到aaccc、aaccf、...、zzzqp、zzzqq。
在給定 N 和 K 之後，給你一個有被列出來的字串 S，請問在剛剛列出的字串當中，S 的下一個字串是什麼？若該字串不存在，則輸出-1。
以第一筆範例測試資料為例，在上面列出的 N = 5,K = 2 的字串當中，aaccc的下一個字串是aaccf、zzzqp的下一個字串是zzzqq，而zzzqq沒有下一個字串。
本題的輸入當中包含多筆測試資料。
輸入的第一行有一個正整數 T，代表有幾筆測試資料。
每筆測試資料共有兩行。第一行包含兩個正整數 N,K，表示殿壬列出的是由g以外的小寫英文字⺟組成⻑度為 N 且恰有 K 個洞的字串。第二行包含一個被殿壬列出的字串 S。
對於每筆測試資料，輸出一行，若 S 的下一個字串存在，則輸出該字串；否則，請輸出
-1。
3 5 2 aaccc 5 2 zzzqp 5 2 zzzqq
aaccf zzzqq -1
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||