Background

Small Reminder

• Pay attention to the letter case of $\texttt{CapsLock}$.

Problem Description

Brief Statement

Repeatedly input $n$ strings, where:

• When the input string is $\texttt{CapsLock}$, the letter case of all subsequent strings is toggled until the next $\texttt{CapsLock}$ appears.
• Given $q$ queries, each query asks for the $x$-th string that is not $\texttt{CapsLock}$.

Original Statement

The Spirit of the Stars can speak $n$ sentences to you, and you need to record them.

Each sentence may be a string not equal to $\texttt{CapsLock}$, or it can be a command $\texttt{CapsLock}$. The command controls the letter case of all letters spoken by the Spirit of the Stars. When $\texttt{CapsLock}$ is spoken once, all lowercase letters spoken afterwards must be changed to uppercase, and all uppercase letters must be changed to lowercase. When $\texttt{CapsLock}$ is spoken the second time, it returns to normal, and so on. In particular, for the $\texttt{CapsLock}$ command spoken by the Spirit of the Stars, you do not need to record it.

The Spirit of the Stars will keep repeating these $n$ sentences without changing the order, and it has $q$ queries. For each query, you need to tell the Spirit of the Stars what the $x$-th sentence you recorded is.

Input Format

This problem uses multiple test cases.

The first line contains an integer $n$.

The next line contains $n$ strings.

The third line contains an integer $q$.

The next $q$ lines each contain a positive integer $x$.

The meanings of $n, q, x$ are as described in the statement.

Output Format

Output $q$ lines, each containing a string, corresponding to the answer for one query.

5
CapsLock CapsLock a CapsLock B
4
1
2
3
4

a
b
A
B

7
h W CapsLock I CapsLock j CapsLock
8
7
9
13
45
20
28
50
101

I
h
H
H
j
j
W
H

10
Oh P CapsLock CapsLock CapsLock Cv Ts CapsLock XU AR 
10
84
63
414
149
25
61
50
4043
9111
47

AR
cV
AR
XU
Oh
Oh
P
XU
cV
XU

Hint

Explanation for Sample #1

The first four recorded sentences are: $a, b, A, B$.

Constraints

For all testdata, $1 \leq n, q \leq 10^5$, $1 \leq x \leq 10^{18}$.

Property $A$: There is no $\texttt{CapsLock}$ among the input strings.

Data Guarantee

• Among all sentences, there is at least one string that is not $\texttt{CapsLock}$.
• The length of every input string is at most $10$.
• All input strings are non-empty and contain only uppercase and lowercase letters.

Translated by ChatGPT 5