Problem Description

There is a programming language as follows.
A program is a sequence of characters representing instructions, executed sequentially from the beginning. The meaning of each character is as follows:

• Lowercase letter $ c $: Output $ c $
• Digit $ x $: Execute the sequence of instructions from the beginning of the program to the instruction immediately before the current one, $ x $ more times

For example, the program ab2c1 outputs the string abababcabababc.

Given a program $ S $. Find the $ X $-th character of the string output by $ S $.

Input Format

Input is given from standard input in the following format:

$ S $ $ X $

Output Format

Output the $ X $-th character of the string output by $ S $.

Sample Input and Output

Sample Input #1

ab2c1
6

Sample Output #1

b

Sample Input #2

atcoder
6

Sample Output #2

e

Sample Input #3

a999999999999999
1000000000000000

Sample Output #3

a

Notes/Hints

Constraints

• $1 \le |S| \le 2 \times 10^5$
• $ S $ consists of lowercase letters and digits from $ 1 $ to $ 9 $
• $1 \le X \le 10^{15}$
• $ S $ outputs at least $ X $ characters

Sample Explanation 1

The program ab2c1 works as follows and outputs the string abababcabababc:
- The first $ 2 $ characters are executed, outputting ab
- The $ 3 $rd character is 2, so the first $ 2 $ characters of $ S $ are executed $ 2 $ more times, outputting abab
- The $ 4 $th character is executed, outputting c
- The $ 5 $th character is 1, so the above $ 3 $ lines are repeated once more, outputting abababc
The final output string is abababcabababc, and its $ 6 $th character is b.

Sample Explanation 2

Since $ S $ contains no digits, it simply outputs atcoder.

Sample Explanation 3

Note that the number of characters output by $ S $ can be very large.

见题面 Input 部分

见题面 Output 部分