The Infinite String
Tag(s):

## Binary search algorithm, Greedy algorithm, Hard

Problem
Editorial
Analytics

You are given N words, each of length at max $50$.
All words consist of small case alphabets and digits 0 to 9.

You concatenate all the N words to form a bigger string A.

An infinite string S is built by performing infinite steps on A recursively:
In $i^{th}$ step, A is concatenated with $''$ i times followed by reverse of A.

$A = A | ... | reverse(A)$, where | denotes concatenation.

Eg: let $A = 123$
Step $1: A = 123321$
Step $2: A = 123321\123321$
And so on… The infinite string thus obtained is S.

You are given Q queries.
For each query, you are given an integer $POS$ and you have to print the character at position $POS$ in the infinite string S.

Input Format
First line contains an integer N, the size of array.
Next line contains N space separated integers $W_1, W_2, … , W_N$.
Next line contains Q, the number of queries.
Q lines follow.
Each line contains an integer $POS$ i.e the position for query.

Output Format
For each query, print the answer in a new line.

Constraints
$1 <= N <= 10^4$
$0 < |W_i| <= 50$
$1 <= Q <= 10^4$
$1 <= POS <= 10^{18}$

SAMPLE INPUT
3
rac 1e ffjn
2
3
10

SAMPLE OUTPUT
c
$ Explanation The string $A = rac1effjn$. The infinite string $S = rac1effjnnjffe1car$….. The $3^{rd}$ character is c. The $10^{th}$ character is $\$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in Challenge Name

National Instruments Intern Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Basic Programming > Input/Output
Notifications

?