GOC11A - Appending String


You are given a string S, you need to build another string T by expanding S according to the steps below (traversing left to right):

  1. If current character is a letter, append it to T.
  2. If current character is a digit, suppose the digit is N, then do T = N*T. Here N*T means appending T N times. See sample for better understanding.
  3. Go to next character if exists then restart from step 1.

Upon expanding S, you will be given Q queries. For each query you have to print the ith character of the string T.

Hint: After expanding the string S = "a3b2c1" T will be = "aaabaaabc"

Input

The first line will be the number of test cases (t <= 10).

In the first line of each test you will be given a string consisting of lowercase letters and digits. And it is guaranteed that length of T will be no more than 1000.

Next line will contain an integer Q (<= 100000) denoting total numbers of queries. Following Q lines each contains an integer X.

Output

For each query X, you have to print the Xth character of T in a line. If X is greater than the length of T, print -1.

Example

Input:
1
a3b2c1
2
4
5

Output:
b
a

hide comments
atul_agarwal: 2016-08-27 20:07:39

should be moved to tutorial

rajat_kumar: 2016-08-27 13:04:57

finally ac

Last edit: 2016-08-27 13:33:12
[Rampage] Blue.Mary: 2016-08-27 03:36:33

What's the range of X? 32-bit signed integer?


Added by:mahbub
Date:2016-08-26
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU