103803: [Atcoder]ABC380 D - Strange Mirroring

Problem Statement

You are given a string $S$ consisting of uppercase and lowercase English letters.

We perform the following operation on $S$ $10^{100}$ times:

• First, create a string $T$ by changing uppercase letters in $S$ to lowercase, and lowercase letters to uppercase.
• Then, concatenate $S$ and $T$ in this order to form a new $S$.

Answer $Q$ queries. The $i$-th query is as follows:

• Find the $K_i$-th character from the beginning of $S$ after all operations are completed.

Constraints

• $S$ is a string consisting of uppercase and lowercase English letters, with length between $1$ and $2 \times 10^5$, inclusive.
• $Q$ and $K_i$ are integers.
• $1 \le Q \le 2 \times 10^5$
• $1 \le K_i \le 10^{18}$

Input

The input is given from Standard Input in the following format:

$S$
$Q$
$K_1$ $K_2$ $\dots$ $K_Q$

Output

Let $C_i$ be the answer to the $i$-th query. Print them in a single line, separated by spaces, in the following format:

$C_1$ $C_2$ $\dots$ $C_Q$

Sample Input 1

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 1

a B A b A b a B A b a B a B A b

Before the operations, $S = $ aB.

• After performing the operation once on aB, it becomes aBAb.
• After performing the operation twice on aB, it becomes aBAbAbaB.
• $\dots$

After performing the operation $10^{100}$ times, $S = $ aBAbAbaBAbaBaBAb...

Sample Input 2

qWeRtYuIoP
8
1 1 2 3 5 8 13 21

Sample Output 2

q q W e t I E Q

Sample Input 3

AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay
5
1000000000000000000 123456789 1 987654321 999999999999999999

Sample Output 3

K a A Z L

问题陈述

给你一个由大写和小写英文字母组成的字符串 $S$。

我们对 $S$ 执行以下操作 $10^{100}$ 次：

• 首先，通过将 $S$ 中的大写字母变为小写，小写字母变为大写，来创建一个字符串 $T$。
• 然后，按照这个顺序将 $S$ 和 $T$ 连接起来，形成一个新的 $S$。

回答 $Q$ 个查询。第 $i$ 个查询如下：

• 找出在所有操作完成后，从 $S$ 开头起的第 $K_i$ 个字符。

约束条件

• $S$ 是一个由大写和小写英文字母组成的字符串，长度在 $1$ 和 $2 \times 10^5$ 之间，包括边界值。
• $Q$ 和 $K_i$ 是整数。
• $1 \le Q \le 2 \times 10^5$
• $1 \le K_i \le 10^{18}$

输入

输入从标准输入以下格式给出：

$S$
$Q$
$K_1$ $K_2$ $\dots$ $K_Q$

输出

设 $C_i$ 为第 $i$ 个查询的答案。按以下格式打印它们，用空格分隔，在一行内：

$C_1$ $C_2$ $\dots$ $C_Q$

示例输入 1

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

示例输出 1

a B A b A b a B A b a B a B A b

操作前，$S = $ aB。

• 在 aB 上执行一次操作后，它变为 aBAb。
• 在 aB 上执行两次操作后，它变为 aBAbAbaB。
• $\dots$

执行 $10^{100}$ 次操作后，$S = $ aBAbAbaBAbaBaBAb...

示例输入 2

qWeRtYuIoP
8
1 1 2 3 5 8 13 21

示例输出 2

q q W e t I E Q

示例输入 3

AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay
5
1000000000000000000 123456789 1 987654321 999999999999999999

示例输出 3

K a A Z L