Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 2538
Dimensional Lookup

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Most modern programming languages are capable of defining multiple dimensional arrays. An N-dimensional array contains zero or more (N-1)-dimensional arrays, each of which can have different length. A plain array (1-dimensional) contains zero or more elements. In our problem we assume that the elements are all positive integers.

ELEMENT ::= positive integer
1-ARRAY ::= { [ ELEMENT (, ELEMENT)* ] }
N-ARRAY ::= { [ N-1-ARRAY (, N-1-ARRAY)* ] }

An N-dimensional query is represented as a list of N integers, namely the indices for each dimension. Index is always zero based. A valid query should point to an element at its end-point.

In this problem you will parse a given array representation and satisfy a query into the array.

Input Description

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each test case is the array representation. The dimension is not given explicitly. The dimension will be at least 1 and at most 100. Length of each dimension does not exceed 100. The total number of elements does not exceed 1,000,000. Space is not important in the array representation and should be ignored. You may assume that the array representation is always valid.

The second line contains the query, which is a list of M (1 <= M <= 100) integers separated with a single space.

Output Description

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

If the query can not be satisfied, print the sentence "Invalid query!" on a single line, otherwise print the value of the element which the query specifies.

Sample Input

3

{1}
0

{{1}, {2, 3}}
1 1

{1, 2, 3}
3

Sample Output

Case 1:
1

Case 2:
3

Case 3:
Invalid query!

Source: Asia 2005, Hangzhou (Mainland China), Preliminary
Submit    Status