問題文

ある英小文字 $C$ について、英小文字からなる空でない文字列 $S$ の $C$ -経験値を、次のように定義します。

• $C$ 以外のある文字が $S$ に重複して現れる場合、 $0$
• そうでない場合、 $S$ に $C$ が現れる回数を $N$ 回として、 $(|S|-N) \\cdot 2^{N}$

例えば、irohachanの $a$ -経験値は $0$ 、chokudaiの $z$ -経験値は $8$ 、experienceの $e$ -経験値は $96$ です。

いろはちゃんは、あなたに $Q$ 個の質問をしてきました。 $i \\ (1 \\leq i \\leq Q)$ 番目の質問は以下の通りです。

質問: $C_i$ -経験値がちょうど $E_i$ である、英小文字からなる空でない文字列は存在するか？存在するのであれば、そのうち辞書順で最小のものは何か？

これら $Q$ 個の質問に順に答えてください。

制約

• $Q, E_i \\ (1 \\leq i \\leq Q)$ は整数
• $C_i \\ (1 \\leq i \\leq Q)$ は英小文字
• $1 \\leq Q \\leq 10^{5}$
• $0 \\leq E_i \\leq 10^{18} \\ (1 \\leq i \\leq Q)$

入力

入力は以下の形式で与えられる。

$Q$ $C_1 \\ E_1$ $C_2 \\ E_2$ $\\vdots$ $C_Q \\ E_Q$

出力

$Q$ 行出力せよ。 $i \\ (1 \\leq i \\leq Q)$ 行目には、 $i$ 番目の質問の答えを、以下に従って出力せよ。

$C_i$ -経験値が $E_i$ である、英小文字からなる空でない文字列が存在しない場合は-1を、存在する場合は、そのような文字列のうち辞書順で最小のものを出力せよ。

この問題において、条件を満たす文字列が存在する場合、その中で辞書順最小のものは一意に定まることが保証される。

入力例1

7
a 48
t 27
c 30
o 1
d 58
e 88
r 800

出力例1

aaaabcd
-1
abcdefghijklmnop
a
-1
abcdeeefghijkl
abcdefghijklmnopqrrrrrstuvwxyz

解説

解説