마지막 주사위의 면 값 정하기

필 크로포트니크(Phil)는 게임 디자이너입니다. 게임을 만들 때 자주 부딪히는 문제 중 하나는 어떤 주사위들을 사용할지 정하는 일입니다. 요즘 많은 게임에서는 전통적인 정육면체(6면) 주사위가 아니라, 면의 수가 더 많거나 적은 특이한 주사위가 필요합니다.

필은 보통 마지막 하나를 제외한 나머지 주사위의 면 값을 먼저 정해 두고, 마지막 주사위의 각 면에 어떤 값을 새기면 특정 합이 원하는 경우의 수만큼 나오도록 만들 수 있는지를 찾습니다. (확률을 다루는 대신, 모든 주사위를 굴렸을 때 어떤 합이 나오는 서로 다른 경우의 수를 직접 다룹니다.) 지금은 이 작업을 손으로 하고 있는데, 이를 자동화하는 것이 여러분의 과제입니다.

여러 개의 주사위를 동시에 굴렸을 때 어떤 합이 나오는 '경우의 수'는, 각 주사위에서 한 면씩 고르는 서로 다른 조합의 개수로 셉니다. 같은 값이 여러 면에 적혀 있더라도, 그 면들은 서로 다른 것으로 구분합니다.

예를 들어, 필이 면 값이 1, 10, 15, 20인 4면 주사위 하나를 이미 가지고 있고, 5면 주사위 하나에 값을 새겨서 두 주사위를 함께 굴린 합이 (a) 합 2가 3가지, (b) 합 3이 1가지, (c) 합 11이 3가지, (d) 합 16이 4가지, (e) 합 26이 1가지 경우로 나오게 하고 싶다고 합시다. 이때 5면 주사위의 면을 1, 1, 1, 2, 6으로 새기면 됩니다. (예를 들어 합 16은 10 + 6 또는 15 + 1로 만들 수 있는데, 두 번째 주사위에는 '1' 면이 세 개이므로 모두 4가지 경우가 됩니다.)

이미 정해진 주사위들, 마지막 주사위의 면 수, 그리고 원하는 (합, 경우의 수) 조건들이 주어질 때, 마지막 주사위의 면 값을 구하세요.

입력은 여러 개의 입력 세트로 이루어집니다. 각 입력 세트는 이미 정해진 주사위의 개수를 나타내는 정수 $n$이 적힌 한 줄로 시작합니다. 이어지는 $n$개의 줄은 각각 주사위 하나를 설명합니다. 각 줄은 그 주사위의 면 수를 나타내는 정수 $f$로 시작하고, 그 뒤에 각 면의 값을 나타내는 $f$개의 정수가 옵니다.

각 세트의 마지막 줄은 다음과 같은 형식입니다.

r m v1 c1 v2 c2 v3 c3 ··· vm cm

여기서 $r$은 값이 정해지지 않은 주사위에 필요한 면 수, $m$은 관심 있는 합의 개수이며, $v_1, \dots, v_m$은 그 합들, $c_1, \dots, c_m$은 각 합을 만들 수 있어야 하는 서로 다른 경우의 수입니다.

입력 값은 다음 제약을 만족합니다: $1 \le n \le 20$, $3 \le f \le 20$, $1 \le m \le 10$, $4 \le r \le 6$. 정해진 주사위와 미지의 주사위 모두, 면에 적히는 값은 $1$부터 $50$까지의 정수입니다. $v_i$와 $c_i$는 모두 음이 아닌 정수이며, 32비트 부호 있는 정수의 최댓값보다 작습니다.

마지막 입력 세트 뒤에는 정수 $0$ 하나만 있는 줄이 오며, 이 줄은 처리하지 않습니다.

각 입력 세트에 대해 다음 중 하나를 한 줄에 출력합니다.

• 조건을 만족하는 주사위가 존재하면, Final die face values are 뒤에 $r$개의 면 값을 감소하지 않는 순서(오름차순)로 출력합니다.
• 조건을 만족하는 주사위가 존재하지 않으면 Impossible을 출력합니다.

조건을 만족하는 주사위가 여러 개라면, 가장 작은 면 값이 가장 작은 것을 선택합니다. 그래도 같으면 두 번째로 작은 면 값이 가장 작은 것을 선택하고, 이런 식으로 계속 비교합니다.