새로운 원소: 파트 2

이 문제에서 이 문단을 제외한 첫 두 문단은 "New Elements: Part 1"의 첫 두 문단과 동일하다. 그 외에는 두 문제를 서로 독립적으로 풀 수 있으며, 한 문제를 읽거나 풀기 위해 다른 문제를 읽거나 풀 필요는 없다.

Muriel은 자신이 Codium과 Jamarium이라고 이름 붙인 두 가지 새로운 원소를 발견하는 과정에 있다. 아직 이들을 분리해 내지는 못했지만, 간접적인 방법으로 원자량과 같은 몇 가지 중요한 성질을 조사하기 시작하려 한다. Muriel은 Codium의 단일 동위원소와 Jamarium의 단일 동위원소를 사용하고 있으므로, 이들의 원자량은 엄격히 양의 정수이다.

Muriel은 서로 다른 N개의 분자를 만드는 데 성공했다. 각 분자는 Codium 원자를 하나 이상, Jamarium 원자를 하나 이상 포함하며, 다른 원소는 포함하지 않는다. 각 분자에 대해 그녀는 각 원소의 원자가 몇 개씩 들어 있는지 알고 있다. 분자의 분자량은 그 분자에 포함된 모든 원자의 원자량을 합한 값이다.

첫 단계로 Muriel은 분자량이 엄격히 증가하도록 분자들을 정렬했다. 이제 그녀는 이 순서와 일치하는 Codium과 Jamarium의 원자량으로 가능한 정숫값을 찾으려 한다. 일치하는 값의 쌍이 많을 수도 있다는 것을 알고 있으므로, 그중 Codium의 원자량을 최소화하는 쌍을 원한다. Codium의 원자량이 최소인 쌍이 여러 개라면, 그중 Jamarium의 원자량이 최소인 쌍을 원한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ 10. 모든 i ≠ j에 대해 ($C_{i}$, $J_{i}$) ≠ ($C_{j}$, $J_{j}$)이다. (모든 분자는 서로 다르다.)

테스트 세트 1 (공개)

모든 i에 대해 1 ≤ $C_{i}$ ≤ 100이다. 모든 i에 대해 1 ≤ $J_{i}$ ≤ 100이다.

테스트 세트 2 (비공개)

모든 i에 대해 1 ≤ $C_{i}$ ≤ $10^{9}$이다. 모든 i에 대해 1 ≤ $J_{i}$ ≤ $10^{9}$이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 분자의 수를 나타내는 정수 N 하나가 주어진다. 이어지는 N개의 각 줄에는 서로 다른 분자 하나가 두 정수 $C_{i}$와 $J_{i}$로 설명되며, 이들은 각각 i번째 분자에 있는 Codium 원자의 수와 Jamarium 원자의 수를 나타낸다. 분자들은 분자량이 엄격히 증가하는 순서로 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 분자량이 엄격히 증가하는 순서가 되게 하는 정수 원자량의 쌍이 없다면 y는 IMPOSSIBLE(대문자)이다. 그렇지 않다면 y은 두 정수 c j이어야 하며, c는 Codium의 원자량이고 j는 Jamarium의 원자량이다. 이들은 위의 규칙에 따라 선택한다.

예제 케이스 #1에서 마지막 두 분자의 차이는 한쪽 원소 또는 다른 쪽 원소의 원자가 하나 더 있다는 것이다. Codium 원자가 더 있는 쪽이 전체적으로 더 무거우므로, Codium이 Jamarium보다 무거워야 한다는 결론을 내릴 수 있다. Codium과 Jamarium의 원자량을 각각 2와 1로 정하면 분자량은 1 × 2 + 1 × 1 = 3, 1 × 2 + 2 × 1 = 4, 그리고 2 × 2 + 1 × 1 = 5가 되어 엄격한 순서를 만족한다. 이 경우 Codium은 Jamarium보다 무거우므로, 2은 Codium의 최소 원자량이고 1은 당연히 Jamarium의 최소 원자량이다.

예제 케이스 #2에 있는 분자들의 분자량을 증가하는 순서대로 a, b, c, d라고 하자. 각 분자의 원자 구성에 따라 d = 2 × a이고 c = 2 × b이다. a < b이므로 d = 2 × a < 2 × b = c가 성립한다. 이는 분자량이 엄격히 증가하는 순서가 되게 하는 원자량 값의 쌍이 없다는 뜻이다.

예제 케이스 #3에서는 분자들이 우연히 전체 원자 수가 엄격히 증가하는 순서로 정렬되어 있음에 유의하라. 따라서 두 원소의 원자량을 모두 1로 정하면 원자량들이 엄격히 증가하는 순서로 정렬된다.