Go Back
Ghost Game (300)
Description

Aman is playing a computer game in which, he is inside a haunted building consisting of N floors.

In order to win the game, he is supposed to reach to the top of the building with the help of the staircases. But while climbing the staircases, everytime he hears a ghost scream, he is supposed to run to the closest floor to him from his current position at that time. In case if both the lower and the upper floors are at an equal distance from him, he dies and the game ends.

Aman knows the number of stairs between each two floors and the total number of stairs he has climbed so far before hearing the ghost scream.
Help him to find the closest floor to him or determine whether the game ends.

Input

The first line of the input consists of a single integer T denoting the number of test cases.
The description of T test cases follow :

The first line of each test case consists of a single integer N denoting the number of floors.

The second line of each test case consists of N space-separated integers.
The ith ( 1 <= i <= N ) of these integers represent the number of stairs between the (i-1)th and the ith floor.
( 0th floor represents the ground floor )

The third line of each test cases consists of a single integer Q denoting the number of queries.
Q lines follow :
Each of these lines consists of a single integer S denoting the total number of stairs Aman has climbed so far before hearing the ghost scream.


Output

For each test case, Output Q lines.
Each of these Q lines should consist of the answer to the corresponding query, which is the closest floor number.
In case if both the lower and the upper floors are at an equal distance from Aman, print “game over” in a single line.

Constraints

1 <= T <= 5
1 <= N <= 10^6
1 <= Q <= 10^5
1 <= Number of stairs between each two floors <= 10^9
1 <= S <= Total number of stairs in the building <= 10^14

Example
Copy Input

Input:
1
4
2 6 3 4
3
5
10
6

Output:
1
game over
2

Explanation

Test Case 1 :
The building has 4 floors.
No. of stairs between 0th and 1st floor -> 2
No. of stairs between 1st and 2nd floor -> 6
No. of stairs between 2nd and 3rd floor -> 3
No. of stairs between 3rd and 4th floor -> 4

Number of Queries - 3
Query - 1 :
S = 5
Therefore, Aman is on the 3rd step between 1st and 2nd floor.
So he is closest to 1st floor.
Query - 2 :
S = 10
Therefore, Aman is on the 2nd step between 2nd and 3rd floor.
So he is equally distant from both the floors, hence game ends.
Query - 3 :
S = 6
Therefore, Aman is on the 4th step between 1st and 2nd floor.
So he is closest to 2nd floor.


Single Round Match #04
3 hour contest



Announcement

Problem Tags
binary search

Supported by our Coding Partner