AT_s8pc_5_h Percepts of Atcoder

[problemUrl]: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_h E869120 は, 文字列を square1001 に今年から $ Q $ 年間, 毎年プレゼントすることにした. 彼は, 文字列 $ S $ が大好きであった. そのため, プレゼントする文字列は, 文字列 $ S $ から取ることに決めた. また, 古から伝わる, AtCoder 社の教えに基づいて, プレゼントする文字列を決めることにした. AtCoder 社の教えは, 以下のようなものである. - 友達に文字列をプレゼントするときは, 以下の方法で文字列を決めなさい. ここでは, あなたの大好きな文字列を $ S $ とおく. - 文字列 $ S $ の部分列の集合を $ T $ とおく. ただし, 文字列 $ S $ の部分列とは, $ S $ から $ 0 $ 個以上の文字を取り去ってできた $ 1 $ 文字以上の長さの文字列のことを指す. - 部分列の集合 $ T $ を辞書順でソートしたときに, $ K $ 番目となる文字列をプレゼントするべきである. 例えば, 大好きな文字列が `aqua` である場合, $ T $ は \[`a`,`aa`,`aq`,`aqa`,`aqu`,`aqua`,`au`,`aua`,`q`,`qa`,`qu`,`qua`,`u`,`ua`\] となる. $ K=10 $ のとき, 辞書順で $ 10 $ 番目となる `qa` をプレゼントするべきである. しかし, $ K $ の値は年ごとに変わってしまう. そこで, $ i $ 年目の $ K $ の値 $ K_i $ が与えられるので, 各年ごとのプレゼントすべき文字列の最後の $ p_i $ 文字を求めてほしい.

入力は以下の形式で標準入力から与えられる. > $ S $ $ Q $ $ K_1 $ $ p_1 $ $ K_2 $ $ p_2 $ $ K_3 $ $ p_3 $ ... $ K_Q $ $ p_Q $

$ Q $ 行出力すること. $ i $ 行目には, $ i $ 年目にプレゼントすべき文字列の最後の $ p_i $ 文字を出力すること. **ただし, 該当する文字列が存在しない場合 "-1" と出力せよ.** **また, プレゼントすべき文字列が $ p_i $ 文字未満の場合, プレゼントすべき文字列をそのまま出力せよ. 例えば, プレゼントすべき文字列が "abcde" であり, $ p_i=7 $ のとき, この行には "abcde" と出力すること.**

### 制約 - $ Q $ は $ 1 $ 以上 $ 100\ 000 $ 以下の整数. - $ S $ は英小文字から成る, $ 1 $ 文字以上 $ 300\ 000 $ 文字以下の文字列. - $ p_i $ は $ 1 $ 以上 $ |S| $ 以下の整数. - $ p_1+p_2+...+p_Q\ \leq\ 1\ 000\ 000 $ - $ K_i $ は $ 1 $ 以上 $ 10^{18} $ 以下の整数. ### 小課題 小課題 $ 1 $ \[$ 210 $ 点\] - $ Q=1 $ を満たす. 小課題 $ 2 $ \[$ 320 $ 点\] - $ K_i\ \leq\ 1\ 000\ 000 $ を満たす. 小課題 $ 3 $ \[$ 870 $ 点\] - 追加の制約はない. ### Sample Explanation 1 問題文の例の通りです. ### Sample Explanation 2 $ 2 $ 個目のクエリにおいて, "tourist" の後ろ $ 4 $ 文字は "rist" なので, これを出力すること.