Fixing Fractions

시간 제한1초메모리 제한1024 MB

요약
두 분수가 주어질 때, 첫 번째 분수의 분자와 분모에서 같은 숫자를 지워 남은 분수가 두 번째 분수와 정확히 같아지는 경우를 찾는다.
난이도

어려움10점 중 8점

유형
문자열, 완전 탐색, 수학, 정수론
정답자
아직 제출이 없습니다

문제

Maths is hard.[citation needed] But it could be easier! And the internet™ has found some excellent ways to make it easier. Take a look at the following true equations:

Following the patterns, we come to the conclusion that the following equation should also be true:\vspace{-0.75\baselineskip}

However, this is actually wrong in boring old standard maths. Therefore, we define a new kind of funky maths where it is allowed to cancel out digits on the left side of the equality sign. This surely will make everyone's life easier. Except yours, since you have to evaluate if two given fractions are equal in our new funky maths.

입력

The input consists of:

  • One line with four integers aa, bb, cc, and dd (1≤a,b,c,d<10181\leq a,b,c,d<10^{18}), describing the two fractions ab\frac{a}{b} and cd\frac{c}{d}.

출력

If there exist integers a′a' and b′b' obtained from aa and bb by cancelling out the same digits and with a′b′=cd\frac{a'}{b'} = \frac{c}{d} in standard mathematics, output "possible", followed by a′a' and b′b'. Otherwise, output "impossible".

If there are multiple valid solutions, you may output any one of them.

Note that neither a′a' nor b′b' is allowed to contain leading zeroes after cancelling digits.

예제3

  1. 예제 1

    입력
    163 326 1 2
    
    예상 출력
    possible
    1 2
    
  2. 예제 2

    입력
    871 1261 13 39
    
    예상 출력
    possible
    87 261
    
  3. 예제 3

    입력
    123 267 12339 23679
    
    예상 출력
    impossible