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 an alphabet, 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 test case number(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


hide comments
nadstratosfer: 2017-10-03 09:00:37

Looked like potentially a WA-nightmare, yet AC at first attempt. No zero's in S, also X is 1-indexed. Nice problem.

hodobox: 2017-08-17 02:56:33

By 'length of T will be no more than 1000' it means the length of the actual string T being built from the input string, NOT the input string. Not only the final length will be small, but also 'intermediate' (while building).

vengatesh15: 2017-03-02 19:19:19

easy one ..

Anand: 2017-01-24 08:01:26

The digit in the string can be 0 too.! Costed me 2 WA

Filip Sollar: 2016-09-20 12:26:28

dont forget -1 if not in range cost me 1 wa

shubham9466: 2016-09-16 14:36:05

Output -1 when x>length of t, costed me a WA! Easy one!!

|RAMSDEN|: 2016-09-13 08:18:04

What's the range of X?

lalit_nit2: 2016-09-01 14:56:28

Last edit: 2016-09-01 14:57:29
prabhakar_jha: 2016-08-31 18:02:20

finally ac :)

Bhumit: 2016-08-30 14:14:21

Can anyone give tricky testcases?
Getting WA in Java :/
Submission ID - 17612957

Last edit: 2016-08-30 14:21:49

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