Find the c-th Character in an Infinite Repeated Compressed String

You are given a string s consisting of lowercase letters and a non-negative integer c. The string s represents a compressed sequence obtained by compressing consecutive same characters. Specifically, a block of k same letters (e.g. aaa...a with k letters) is compressed to the format ak. For example, aaaabccdddd is compressed as a4b1c2d4.

The complete uncompressed string is formed by decoding the compressed string and then considering this string repeated infinitely. The task is to determine the character at the c-th position (0-indexed) of this infinite repeated string. Formally, if the uncompressed string is denoted by \(S\) (with \(S_0\) as the first character), find \(S_{(c \bmod L)}\), where \(L\) is the length of the uncompressed string.

Note: Use \(\LaTeX\) format for any formulas. You can assume that the input is always valid and the compressed string follows the described format.

inputFormat

The input consists of a single line containing the compressed string s and the non-negative integer c, separated by a space.

Example:

a4b1c2d4 7

outputFormat

Output the character at the c-th position (0-indexed) in the infinite repeated uncompressed string.

Example:

d

sample

a4b1c2d4 0

a