問題一覧 > 通常問題

No.3317 Waronganswerronganswernswaronger

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 31
作問者 : elphe / テスター : ゆにたりー卿 Rice_tawara459 DeltaStruct kazuppa Andrew8128 のらら 👑 みうね 👑 loop0919 👑 seekworser
お気に入りにしたユーザー ProblemId : 11979 / 自分の提出
問題文最終更新日: 2025-10-30 09:43:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
第2回 岩井星人アンソロジープログラミングコンテスト Div.1 (順位表) の他の問題:

Problem Statement

An alien from Planet Iwai smuggled a string $S$ of length $N$ consisting of lowercase English letters from Earth to Planet Iwai.
However, on Planet Iwai, there is a property that every $1$ second, "each w in a string is replaced with warong, and each a is replaced with answer", so the smuggled string $S$ covered Planet Iwai in no time.
Here, it is known that the $1$st replacement of the smuggled string $S$ occurred exactly $1$ second after the string $S$ was brought to Planet Iwai.
Judging that the situation is already out of control, you decided to process the following $Q$ queries in order to simulate the impact on Planet Iwai.
For the $i$-th query, answer the following question correctly.

What is the $X_i$-th character of $S$ at $(T_i + 0.1)$ seconds after the string $S$ was brought to Planet Iwai (that is, immediately after the $T_i$-th replacement)?

Constraints

  • $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)$ are all integers.
  • The given string $S$ is the string at the time it was brought to Planet Iwai.
  • The given string $S$ is a string of length $N$ consisting of lowercase English letters.
  • The given string $S$ contains at least $1$ w or a.
  • The length of $S$ at $(T_i + 0.1)$ seconds after the string $S$ was brought to Planet Iwai is at least $X_i$ characters $(1 \leq i \leq Q)$.

Input

Input is given from standard input in the following format. 
$N$ $Q$
$S$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_Q$ $X_Q$

Output

Answer the $Q$ queries in the given order, and print the results as a string of $Q$ characters on $1$ line.
The $i$-th character must be the answer to the $i$-th query.

Sample

Sample 1
Input
2 3
wa
1 1
1 10
2 25
Output
www

The string $S$ changes as follows: wa → waronganswer → waronganswerronganswernswaronger → ...

  • The $1$st character of waronganswer is w.
  • The $10$th character of waronganswer is w.
  • The $25$th character of waronganswerronganswernswaronger is w.
Concatenate these $3$ characters in this order and print them as a string of $Q (= 3)$ characters on $1$ line.
Note that different queries may have the same answer.

Sample 2
Input
8 8
chokudai
8 17
7 641
6 6
5 1
4 78
3 6
2 21
1 12
Output
redcoder

The given string $S$ may contain only one of w and a.
The queries are not necessarily given in ascending order of $T_i$ or of $X_i$.

The string $S$ changes as follows: chokudai → chokudansweri → chokudanswernswarongeri → ...

  • The $17$th character of $S$ at $8.1$ seconds after it was brought to Planet Iwai is r.
  • The $641$st character of $S$ at $7.1$ seconds after it was brought to Planet Iwai is e.
  • The $6$th character of $S$ at $6.1$ seconds after it was brought to Planet Iwai is d.
  • The $1$st character of $S$ at $5.1$ seconds after it was brought to Planet Iwai is c.
  • The $78$th character of $S$ at $4.1$ seconds after it was brought to Planet Iwai is o.
  • The $6$th character of $S$ at $3.1$ seconds after it was brought to Planet Iwai is d.
  • The $21$st character of $S$ at $2.1$ seconds after it was brought to Planet Iwai is e.
  • The $12$th character of $S$ at $1.1$ seconds after it was brought to Planet Iwai is r.
Concatenate these in this order into $1$ string and print it on $1$ line.
Note that the order in which the queries must be answered is specified.

Also, the answers to queries $1,2,7,8$ are characters not contained in the string chokudai.
Be careful of such cases, where the answer is a character not in the given string $S$.

Sample 3
Input
5 5
yiwiy
1000000000000000000 999999999999999992
1000000000000000000 999999999999999999
1000000000000000000 999999999999999993
1000000000000000000 999999999999999993
1000000000000000000 999999999999999995
Output
green

No matter how many seconds pass, c never appears in $S$, so the string to be printed can never be cyan.
The string $S$ changes as follows: yiwiy → yiwarongiy → yiwaronganswerrongiy → yiwaronganswerronganswernswarongerrongiy → ...

  • The $(10^{18} - 8)$-th character of $S$ at $(10^{18} + 0.1)$ seconds after it was brought to Planet Iwai is g.
  • The $(10^{18} - 1)$-th character of $S$ at $(10^{18} + 0.1)$ seconds after it was brought to Planet Iwai is r.
  • The $(10^{18} - 7)$-th character of $S$ at $(10^{18} + 0.1)$ seconds after it was brought to Planet Iwai is e.
  • The $(10^{18} - 7)$-th character of $S$ at $(10^{18} + 0.1)$ seconds after it was brought to Planet Iwai is e.
  • The $(10^{18} - 5)$-th character of $S$ at $(10^{18} + 0.1)$ seconds after it was brought to Planet Iwai is n.
As shown here, the values of $T_i,\ X_i$ may not fit in a $32\mathrm{bit}$ variable.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。