No.3317 ワロングアンサーロングアンサーンスワロンガー
タグ : / 解いたユーザー数 29
作問者 :
elphe
/ テスター :
高橋ゆに
こめだわら
DeltaStruct
kazuppa
Andrew8128
のらら
みうね
👑 
loop0919
seekworser
問題文
ある岩井星人は地球から、半角英小文字からなる長さ $N$ の文字列 $S$ を岩井星に密輸しました。
ところが、岩井星では $1$ 秒毎に「文字列の w の部分が warong に、a の部分が answer にそれぞれ置き換わる」という性質があり、密輸した文字列 $S$ が岩井星をあっという間に覆い尽くしてしまいました。
ここで、密輸した文字列 $S$ の $1$ 回目の置換が発生したのは、文字列 $S$ が岩井星に持ち込まれてからちょうど $1$ 秒後の出来事であったことがわかっています。
もはや手に負えないと判断したあなたは、岩井星への影響をシミュレーションするため、以下の $Q$ 個のクエリを処理することにしました。
$i$ 個目のクエリでは、次の質問に正しく回答してください。
文字列 $S$ が岩井星に持ち込まれてから $(T_i + 0.1)$ 秒後（つまり $T_i$ 回目の置換の直後）の $S$ の $X_i$ 文字目は何ですか？
制約
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 10^5$
- $1 \leq T_i \leq 10^{18}$
- $1 \leq X_i \leq 10^{18}$
- $N,\ Q,\ T_i,\ X_i \ (1 \leq i \leq Q)$ はいずれも整数
- 与えられる文字列 $S$ は岩井星に持ち込まれた時点の文字列
- 与えられる文字列 $S$ は英小文字からなる長さ $N$ の文字列
- 与えられる文字列 $S$ は
wまたはaを少なくとも $1$ つ含む - 文字列 $S$ が岩井星に持ち込まれてから $(T_i + 0.1)$ 秒後の $S$ は $X_i$ 文字以上 $(1 \leq i \leq Q)$
入力
入力は以下の形式で標準入力から与えられる。$N$ $Q$ $S$ $T_1$ $X_1$ $T_2$ $X_2$ $\vdots$ $T_Q$ $X_Q$
出力
$Q$ 個のクエリを与えられた順に回答し、その結果を $Q$ 文字の文字列として $1$ 行に出力せよ。
$i$ 文字目は $i$ 個目のクエリの回答とせよ。
サンプル
サンプル1
入力
2 3 wa 1 1 1 10 2 25
出力
www
文字列 $S$ の変化を記述すると、
wa → waronganswer → waronganswerronganswernswaronger → ... となり、
waronganswerの $1$ 文字目はwです。waronganswerの $10$ 文字目はwです。waronganswerronganswernswarongerの $25$ 文字目はwです。
異なるクエリでも同じ答えになる可能性があることに注意してください。
サンプル2
入力
8 8 chokudai 8 17 7 641 6 6 5 1 4 78 3 6 2 21 1 12
出力
redcoder
与えられる文字列 $S$ には w と a の片方しか含まれていない場合があります。
クエリは $T_i$ の昇順や $X_i$ の昇順に与えられるとは限りません。
文字列 $S$ の変化を記述すると、chokudai → chokudansweri → chokudanswernswarongeri → ... となり、
- 岩井星に持ち込まれてから $8.1$ 秒後の $S$ の $17$ 文字目は
rです。 - 岩井星に持ち込まれてから $7.1$ 秒後の $S$ の $641$ 文字目は
eです。 - 岩井星に持ち込まれてから $6.1$ 秒後の $S$ の $6$ 文字目は
dです。 - 岩井星に持ち込まれてから $5.1$ 秒後の $S$ の $1$ 文字目は
cです。 - 岩井星に持ち込まれてから $4.1$ 秒後の $S$ の $78$ 文字目は
oです。 - 岩井星に持ち込まれてから $3.1$ 秒後の $S$ の $6$ 文字目は
dです。 - 岩井星に持ち込まれてから $2.1$ 秒後の $S$ の $21$ 文字目は
eです。 - 岩井星に持ち込まれてから $1.1$ 秒後の $S$ の $12$ 文字目は
rです。
クエリの回答順が指定されていることに注意してください。
また、$1,2,7,8$ 個目のクエリは、文字列 chokudai に含まれない文字が答えになっています。
このように、与えられた文字列 $S$ 中にない文字が答えになる場合に注意してください。
サンプル3
入力
5 5 yiwiy 1000000000000000000 999999999999999992 1000000000000000000 999999999999999999 1000000000000000000 999999999999999993 1000000000000000000 999999999999999993 1000000000000000000 999999999999999995
出力
green
何秒経っても $S$ に c が現れないため、出力すべき文字列は cyan になりえません。
文字列 $S$ の変化を記述すると、yiwiy → yiwarongiy → yiwaronganswerrongiy → yiwaronganswerronganswernswarongerrongiy → ... となり、
- 岩井星に持ち込まれてから $(10^{18} + 0.1)$ 秒後の $S$ の $(10^{18} - 8)$ 文字目は
gです。 - 岩井星に持ち込まれてから $(10^{18} + 0.1)$ 秒後の $S$ の $(10^{18} - 1)$ 文字目は
rです。 - 岩井星に持ち込まれてから $(10^{18} + 0.1)$ 秒後の $S$ の $(10^{18} - 7)$ 文字目は
eです。 - 岩井星に持ち込まれてから $(10^{18} + 0.1)$ 秒後の $S$ の $(10^{18} - 7)$ 文字目は
eです。 - 岩井星に持ち込まれてから $(10^{18} + 0.1)$ 秒後の $S$ の $(10^{18} - 5)$ 文字目は
nです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。