H - 〔経験値〕 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ある英小文字 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

解説

解説