(This is an implementation of the official editorial’s section “We can follow this step until we reach \(B=0\) to get the correct answer” using recursion.)

Let the length of \(S\) be \(N\), and call the string obtained by applying the operation described in the problem to \(S\) \(l\) times as the level \(l\) string. Each time the operation is performed, the length of the string doubles, so the length of the level \(l\) string is \(2^l \times N\), and given the constraint \(K_i \leq 10^{18}\), it suffices to consider the level \(60\) string.

In the level \(0\) string, the \(k\)-th character is the \(k\)-th character of \(S\).

In the level \(l\) string (\(l \geq 1\)), noting that the first half of this string matches the level \(l-1\) string and the second half is obtained by changing the case of letters in that string, the \(k\)-th character is as follows:

• If \(k \leq 2^l \times N\), then it’s the \(k\)-th character of the level \(l-1\) string.
• Otherwise, it’s the character obtained by changing the case of the \((k - 2^{l-1} \times N)\)-th character of the level \(l-1\) string.

This can be implemented directly as a recursive function.

Sample Implementation (Python):

S = input()
Q = int(input())
K = map(int, input().split())

def f(k, l):
    if l == 0:
        return S[k - 1]
    h = len(S) << (l - 1)
    if k <= h:
        return f(k, l - 1)
    return chr(ord(f(k - h, l - 1)) ^ 32)

for k in K:
    print(f(k, 60), end=" ")