CCC '25 S2 - Cryptogram Cracking Club

Canadian Computing Competition: 2025 Stage 1, Senior #2

Cyrene, the captain of the Cryptogram Cracking Club (CCC), came across a concerningly long cipher. Conveniently, this cipher is composed of lower-case characters (a-z). Comfortingly, the cipher is composed of a pattern that repeats infinitely.

Cyrene wishes to locate the c-th character of the cipher. To make your job easier, the CCC members have extracted the repeated pattern and compressed it using the Run-Length Encoding (RLE) algorithm, which replaces consecutive repeated characters with a single occurrence of the character followed by a count of how many times it was repeated. For example, for the pattern aaaabccdddd, the RLE algorithm outputs a4b1c2d4.

You are given the output of the RLE algorithm for a certain pattern. Can you determine the c-th character of the long cipher that is formed by repeating this pattern infinitely?

Input Specification

The first line of input will consist of a string S, representing a pattern produced by the RLE algorithm. The length of S will be at least 2 and at most 2 * 10^5. Additionally, all numbers appearing in S are between 1 and 10^12.

The next line of input contains a single integer c, representing the index of the character you wish to locate, starting from index 0.

The following table shows how the available 15 marks are distributed:

Output Specification

Output the c-th character of the long cipher.

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

The output of the RLE algorithm r2d2 corresponds to the pattern rrdd, which creates the infinitely long cipher rrddrrddrrddrrdd..., where the c = 8th character is r. In this example, the c = 8th character is highlighted with a box around it.

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

The output of the RLE algorithm a4b1c2d10 corresponds to the pattern aaaabccdddddddddd. When repeated infinitely, the c = 100th character is d.