Butterfly Ballots

To improve a candidate's odds of winning an election, it helps to have allies on the election board. One classic trick is the butterfly ballot. On a butterfly ballot every candidate's name is printed down one side (say the left) and every box in which to mark a vote is printed down the other side. When the boxes are shifted just slightly, it becomes hard to tell which box belongs to which candidate, so an inattentive voter can easily mark the box next to the wrong candidate.

You must design a ballot that makes your candidate win, if that is possible. Every candidate must appear on the ballot, in some top-to-bottom order that you choose. The boxes sit on the other side, offset by half a row: the first box is above the first candidate, the second box is between the first and second candidate, and so on. As a result, among the voters who intend to vote for the candidate at position $i$ on your ballot, half actually vote for that candidate and half accidentally vote for the candidate at position $i + 1$ (the one just below). The voters who intend to vote for the last candidate on the ballot all vote correctly.

Your candidate is candidate $1$ in the input. Decide whether some ordering makes candidate $1$ finish with at least as many votes as every other candidate. A tie for first place also counts as a win.

The first line contains an integer $K \ge 1$, the number of data sets. Each of the $K$ data sets follows.

The first line of a data set contains an integer $n$ with $1 \le n \le 100$, the number of candidates. Candidate $1$ is the one you are trying to make win. The next $n$ lines each contain an integer $v_i$, the number of voters who intend to vote for candidate $i$. Every $v_i$ is even, so halving is always exact.

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set's number. Then print Possible on a line by itself if candidate $1$ can be made to win, or Impossible otherwise.