나비 투표용지

나비 투표용지는 후보 이름을 한쪽 열에 세로로 적고, 기표란은 반대쪽 열에 놓는다. 두 열이 반 칸씩 어긋나 있으면 어느 기표란이 어느 후보의 것인지 알아보기 어렵다. 아래 용지에서는 USC를 찍으려던 사람이 UCLA의 기표란에 표시하기 쉽다. 선거에서도 같은 일이 일어난다.

당신은 자신의 후보를 1위로 만드는 투표용지를 설계한다. 후보 $n$명을 모두 용지에 올려야 하고, 위에서 아래로 놓는 순서는 마음대로 정할 수 있다. 기표란은 반대쪽 열에 놓인다. 첫 번째 기표란은 첫 번째 후보보다 위에 있고, 두 번째 기표란은 첫 번째 후보와 두 번째 후보 사이에 있으며, 그 뒤도 같은 방식으로 이어진다.

그래서 위에서 $i$번째 자리에 놓인 후보를 찍으려던 유권자는 절반이 그 후보에게 제대로 투표하고, 나머지 절반이 한 칸 아래인 $i+1$번째 자리의 후보에게 잘못 투표한다. 맨 아래 자리에 놓인 후보를 찍으려던 유권자는 모두 제대로 투표한다.

후보 1번이 당신의 후보다. 후보 1번이 1위가 되는 순서가 있는지 판정하라. 후보 1번이 공동 1위여도 이긴 것으로 본다.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. $K \ge 1$이다.

이어서 데이터 집합 $K$개가 주어진다. 각 데이터 집합의 첫 줄에는 용지에 오를 후보 수 $n$이 주어진다. $1 \le n \le 100$이고, 후보 1번이 당신이 당선시키려는 후보다. 다음 $n$개 줄에는 후보 $i$를 찍으려는 유권자 수 $v_i$가 한 줄에 하나씩 주어진다. $1 \le v_i \le 10^6$이며, $v_i$는 모두 짝수라서 2로 나누어떨어진다.

데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호다. 후보 1번을 1위로 만들 수 있으면 다음 줄에 Possible을, 만들 수 없으면 Impossible을 출력한다. 각 데이터 집합의 출력 뒤에는 빈 줄을 한 줄 출력한다.