문제
이진수 110(2)을 생각해 보자. 110(2)을 일반적인 이진수 연산으로 계산하면 4*1 + 2*1 + 1*0 = 6이 되지만 110(2)의 각 자리의 가중치를 음수로 계산하면 (-4) * 1 + (-2)*1 + (-1)*0 = -6이 된다.
이러한 평범한 이진수 연산을 마스터한 서현이는 새로운 이진수 연산을 생각해 내었다. 음수 가중치와 양수 가중치를 섞어서 어떤 원하는 수를 만들 수 있을까?
예를 들어 이진수의 자리 수가 4이고 각 자리수의 가중치에 대한 정보가 ppnn (p는 양수 가중치, n은 음수 가중치) 만들고자 하는 십진수가 10 이라고 할 때, 이를 만족하는 이진수는 1110(2) 이 된다. 1110(2) = 8*1 + 4*1 + (-2)*1 + (-1)*0 => 10(10)
또 다른 예로, 이진수의 자리 수가 3이고 각 자리수의 가중치에 대한 정보가 pnp (p는 양수 가중치, n은 음수 가중치) 만들고자 하는 십진수가 6 이라고 할 때, 이를 만족하는 이진수는 없다. 이 경우 Impossible을 출력한다.
입력
첫 행에 테스트 케이스의 개수 T( 1 ≤ t ≤ 10) 이 입력된다.
다음 행에 이진수의 자리 수 K( 1 ≤ K ≤ 64)가 입력된다. 다음 행에 각 자리수의 가중치에 대한 정보가 입력된다.
다음 행에 만들고자 하는 십진 정수 N( -263 ≤ N < 263 )
출력
각 테스트 케이스에 대하여 행으로 구분하여 가능한 이진수를 출력한다. 가능한 경우가 여러 가지인 경우 그 중 한 가지만 출력한다. 불가능한 경우 Impossible을 출력한다.
예제
2
3
pnp
6
4
ppnn
10
Impossible
1110
로그인해야 코드를 작성할 수 있어요.