Find the K-th Character in String Game II

Hard

Alice and Bob are playing a game. Initially, Alice has a string word = "a" .

You receive a positive integer k . You are also given an integer array operations , where operations[i] represents the type of the i th operation.

Now Bob will ask Alice to perform all operations in sequence:

If operations[i] == 0 , append a copy of word to itself.
If operations[i] == 1 , generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word . For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac" .

Produce the value of the k th character in word after performing all the operations.

Note that the character 'z' can be changed to 'a' in the second type of operation.

Example 1

Input: k = 5, operations = [0,0,0]

Output: "a"

Explanation: For this case, initially, word == "a" . Alice performs the three operations as follows:

Example 2

Input: k = 10, operations = [0,1,0,1]

Output: "b"

Explanation: For this case, initially, word == "a" . Alice performs the four operations as follows:

Constraints

1 <= k <= 10^14
1 <= operations.length <= 100
operations[i] is either 0 or 1.
The input is generated such that word has at least k characters after all operations.

Responses stay private.