부분 변환

당신은 나라에서 가장 뛰어난 연금술사이기에, 과학을 넘어선 힘으로 희귀 금속에 대한 나라 지도자의 끝없이 커지는 탐욕을 충족해야 해서 또다시 소환되었다.

각 금속은 양의 정수로 나타낸다. 금속 $1$을 $\mathbf{U_1}$단위, 금속 $2$을 $\mathbf{U_2}$단위, $\ldots$ 그리고 금속 $\mathbf{N}$을 $\mathbf{U_N}$단위 만들어야 한다. 금속 $\mathbf{N}+1, \mathbf{N}+2, \ldots$도 존재하지만, 그 금속들을 특정한 양만큼 만들 필요는 없다. 어떤 금속이든 필요한 양보다 더 많이 만들어도 되며, 남는 양은 그냥 버릴 수 있다.

안타깝게도 예산 삭감으로 인해 간단한 연금술 주문을 위한 재료만 남았다. $\mathbf{A} \lt \mathbf{B}$인 어떤 고정된 수 $\mathbf{A}$와 $\mathbf{B}$에 대해, 금속 $i$ 한 단위를 가져와 파괴하여 금속 $(i-\mathbf{A})$ 한 단위와 금속 $(i-\mathbf{B})$ 한 단위를 만들 수 있다. 이 두 정수 중 하나가 양수가 아니라면 해당 단위는 만들어지지 않는다. 특히 $i \le \mathbf{A}$이면 주문은 그 단위를 파괴하기만 하고 아무것도 만들지 않는다. $\mathbf{A} \lt i \le \mathbf{B}$이면 주문은 그 단위를 파괴하고 금속 $(i-\mathbf{A})$ 한 단위만 만든다.

당신을 돕기 위해 전문 광부 한 명이 배정되었다. 전문 광부는 당신이 원하는 어떤 금속이든 한 단위를 가져올 수 있다. 그 단위에서 시작하여 주문으로 다른 금속들을 만든 다음, 그렇게 만들어진 금속들에 다시 주문을 사용해 훨씬 더 많은 단위를 만들 수 있다. 아래 그림은 $\mathbf{A}=1$와 $\mathbf{B}=2$인 주문을 두 번 사용하여 금속 $4$ 한 단위를 금속 $1$ 한 단위와 금속 $2$ 두 단위로 바꾸는 모습을 보여 준다.

더 큰 정수로 나타내는 금속일수록 더 무겁고 다루기 어려우므로, 작업을 완료하기에 충분한 금속 중 가능한 가장 작은 정수로 나타내는 금속 한 단위를 전문 광부에게 요청하거나, 그러한 금속이 없다고 말하고자 한다.

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 20$. 모든 $i$에 대해 $0 \le \mathbf{U_i} \le 20$. $1 \le \mathbf{U_N}$. $2 \le \mathbf{U_1} + \mathbf{U_2} + \cdots + \mathbf{U_N}$.

테스트 세트 1 (Visible Verdict)

$\mathbf{A} = 1$. $\mathbf{B} = 2$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{A} \lt \mathbf{B} \le 20$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 세 정수 $\mathbf{N}$, $\mathbf{A}$, $\mathbf{B}$가 주어지며, 각각 만들어야 하는 금속 번호 중 가장 큰 번호와 위에서 설명한 사용 가능한 주문을 정의하는 두 값을 나타낸다. 테스트 케이스의 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{U_1}, \mathbf{U_2}, \ldots, \mathbf{U_N}$가 주어지며, 각각 금속 $1, 2, \ldots, \mathbf{N}$의 필요한 단위 수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, 금속 한 단위에서 시작하여 필요한 모든 단위를 만들 수 없다면 $y$는 IMPOSSIBLE이다. 그렇지 않으면 $y$는 그 금속 한 단위로 필요한 모든 금속 단위를 만들기에 충분한 금속을 나타내는 가장 작은 정수이다.

예제 케이스 #1에서는 금속 $1$ 한 단위와 금속 $2$ 두 단위가 필요하다. 금속 $3$ 한 단위로 시작하여 주문을 한 번 적용하면 금속 $1$ 한 단위와 금속 $2$ 한 단위를 얻는다. 금속 $2$ 한 단위를 추가로 얻을 방법은 없다. 마찬가지로 금속 $1$ 또는 $2$ 한 단위로 시작하는 것도 충분하지 않다. 하지만 문제 본문의 그림에서 보여 주듯이 금속 $4$ 한 단위는 충분하다.

예제 케이스 #2에서는 금속 $6$ 한 단위로 시작하여 다음 연산들을 적용할 수 있다.

• $6$에 주문을 적용한다: $\{6\} \longrightarrow \{4, 5\}$.

• $4$에 주문을 적용한다: $\{4, 5\} \longrightarrow \{2, 3, 5\}$.

• $2$에 주문을 적용한다: $\{2, 3, 5\} \longrightarrow \{1, 3, 5\}$.

• $3$에 주문을 적용한다: $\{1, 3, 5\} \longrightarrow \{1, 1, 2, 5\}$.

금속 $2$ 한 단위가 남더라도 이 해법은 유효하다는 점에 유의한다.

예제 케이스 #3에서는 금속 $5$ 한 단위로 시작하여 다음 연산들을 적용할 수 있다.

• $5$에 주문을 적용한다: $\{5\} \longrightarrow \{3, 4\}$.

• $4$에 주문을 적용한다: $\{3, 4\} \longrightarrow \{2, 3, 3\}$.

• $2$에 주문을 적용한다: $\{2, 3, 3\} \longrightarrow \{1, 3, 3\}$.

• $3$에 주문을 적용한다: $\{1, 3, 3\} \longrightarrow \{1, 1, 2, 3\}$.

주문을 적용하여 성공할 수 있는 다른 방법들도 있지만, 그 방법들은 모두 금속 $5$ 이상인 금속 한 단위로 시작해야 한다.

추가 예제 - 테스트 세트 2

테스트 세트 2의 첫 번째 예제 케이스에서는 어떤 금속이든 그 한 단위로 시작하여 $\mathbf{A}=2$와 $\mathbf{B}=4$인 주문을 여러 번 적용한 뒤 금속 $1$, $2$, $3$을 각각 한 단위씩 남기는 것이 불가능하다.