给定一个字符串 S S，由大写和小写英文字母组成。

我们对 S 进行10的100次方 次执行以下操作：

首先，通过将 S 中的大写字母转换为小写字母，将小写字母转换为大写字母，创建一个字符串 T。 然后，按照此顺序连接 S和 T形成一个新的 S。 回答 Q Q 个查询。第 i i 个查询如下：

在所有操作完成后，从 S 的开头找到第 Ki个字符。 约束条件 S S 是一个由大写和小写英文字母组成的字符串，长度在 1 到 2×10的5次方之间（包括两者）。 Q Q 和 Ki是整数。 1≤Q≤2×10的5次方 1≤ Ki≤10的18次方 示例 1 Inputcopy Outputcopy aB 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 a B A b A b a B A b a B a B A b 在执行操作之前， S

S= aB。

对 aB 执行一次操作后，变为 aBAb。 对 aB 执行两次操作后，变为 aBAbAbaB。 … … 执行 1 0 100 10 100 次操作后， S

S= aBAbAbaBAbaBaBAb...

示例 2 Inputcopy Outputcopy qWeRtYuIoP 8 1 1 2 3 5 8 13 21 q q W e t I E Q 示例 3 Inputcopy Outputcopy AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay 5 1000000000000000000 123456789 1 987654321 999999999999999999 K a A Z L