Do you know how Digo grew up to be so poor? There is a long story. Once upon a time, there lived a rich landlord named Dogo in a prosperous village of CodeVillage. He had three children, a boy and two girls. The boy was none other than Digo. Digo was very bad tempered when he was small, so he used to tease his own sisters. Now one day Dogo died. The time to divide his property came. The two sisters decided to take revenge.
The division took place by the following rules...
First, all the property was written down sequentially on a paper, then digo was asked to tear the paper in two parts. Then second sister was asked to tear any one of the two parts in two new parts thus forming total three parts. Then First sister will select any one part. Then the Second sister will select any one of the remaining two and leaving the third part if the property with Digo.
Since the sisters dont like Digo, their move will be such that they want to maximize their own part and then to minimize Digo's.
Now help Digo to select his move optimaly, such that he gets maximum possible share.
First line contains t, no. of testcases.
t testcases follow,
For each testcase, their are 2 lines.
First line contains n, number of goodies in property list.
Next line contains n space separated numbers, the value of corresponding goody.
t lines, each having an integer, the maximum amount Digo can get.
In first case, if Digo cuts as 5th pos, the sister will cut at 7th(To maximize her part '6') and digo will get 5, if digo tries to increase and cut at 6, sister will cut at last index givin Digo 1 and herself 6.