Flammable Railway 997

A passenger is riding in one car of Flammable Railway 997.

Every car of this train explodes when it catches fire. If a car explodes at time t, then at time t+1 the fire tries to move to the neighboring cars on the left and right. If there is any fireproof material left between two cars, one unit of that material is consumed and the fire does not cross in that direction. If no fireproof material remains, the neighboring car explodes at time t+1.

The same car may explode multiple times, but at most once at the same time. For example, even if cars 2 and 4 exploded at the previous time, car 3 explodes only once at the next time.

The passenger is in danger at the moment their car explodes. Given the amount of fireproof material between cars and the car where the first fire starts, determine the time when the passenger's car explodes.

The train cars are numbered from 0 through n. Cars 0 and 1 are directly connected, and there is no fireproof material between them. The initial fire car k and the passenger's car c are both between 1 and n, inclusive.

The first line contains the number of test cases T. T is at most 100.

Each test case is given on one line as n, k, c, followed by n-1 integers. k is the car where the fire starts, and c is the passenger's car. The i-th of the following n-1 integers is the amount of fireproof material between cars i and i+1.

n is at most 1,000, and every integer in the input fits in the int range.

For each test case, print the time when the passenger's car explodes. If that car can never explode, print gg.