J - 長い長い文字列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

以下のようなプログラミング言語があります。
プログラムは命令を表す文字の列であり、前から順に実行されます。各文字が表す命令の意味は下の通りです。

  • 英小文字 c : c を出力する
  • 数字 x : プログラムの先頭から、現在実行中の命令の一つ前の命令までの命令列を、もう x 回実行する

例えば、プログラム ab2c1 は文字列 abababcabababc を出力します。

プログラム S が与えられます。S が出力する文字列の X 番目の文字を求めてください。

制約

  • 1 \le |S| \le 2 \times 10^5
  • S は英小文字及び 1 以上 9 以下の数字からなる
  • 1 \le X \le 10^{15}
  • S は X 文字以上出力する

入力

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

S
X

出力

S が出力する文字列の X 番目の文字を出力せよ。

入力例 1

ab2c1
6

出力例 1

b

プログラム ab2c1 は以下のように動作し、文字列 abababcabababc を出力します。

  • 最初の 2 文字が実行されて、ab が出力される
  • 3 文字目に 2 があるので、S の最初の 2 文字がもう 2 回実行され、abab が出力される
  • 4 文字目が実行され、c が出力される
  • 5 文字目に 1 があるので、上の 3 行がもう一度繰り返され、abababc が出力される

出力される文字列は最終的に abababcabababc であり、この 6 文字目は b です。

入力例 2

atcoder
6

出力例 2

e

S に数字が含まれていないので、そのまま atcoder が出力されます。

入力例 3

a999999999999999
1000000000000000

出力例 3

a

S が出力する文字数は非常に大きくなることがあることに注意してください。

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Consider the following programming language:

A program is a sequence of characters, each representing an instruction, executed from left to right. Each character represents the following instruction:

  • A lowercase English letter c: print c.
  • A digit x: Execute the following x more times: the subsequence of instructions from the beginning of the program through the instruction immediately before the current instruction.

For example, the program ab2c1 prints the string abababcabababc.

Given a program S, find the X-th character of the string printed by S.

Constraints

  • 1 \le |S| \le 2 \times 10^5
  • S consists of lowercase English letters and digits from 1 through 9.
  • 1 \le X \le 10^{15}
  • S prints at least X characters.

Input

Input is given from Standard Input in the following format:

S
X

Output

Print the X-th character of the string printed by S.

Sample Input 1

ab2c1
6

Sample Output 1

b

The program ab2c1 runs as follows and prints the string abababcabababc.

  • The first two characters print ab.
  • The third character 2 executes the first two characters two more times and prints abab.
  • The fourth character prints c.
  • The fifth character 1 performs the process described by the above three lines and prints abababc.

In the end, the program prints the string abababcabababc, whose 6-th character is b.

Sample Input 2

atcoder
6

Sample Output 2

e

S contains no digit, so it just prints atcoder.

Sample Input 3

a999999999999999
1000000000000000

Sample Output 3

a

Note that S can print extremely many characters.