D - Strange Mirroring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

英大小文字からなる文字列 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

出力

i 個目の質問の答えを C_i とする時、以下の形式で 1 行に空白区切りで出力せよ。

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 に 1 回操作を行うと aBAb となります。
  • aB に 2 回操作を行うと 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

Score : 350 points

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