만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

페티는 없다

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

요약
n과 k가 주어질 때, Yatep의 시트에 적힌 수 중 차이가 정확히 k인 두 수를 찾거나 불가능하다고 출력합니다.
난이도

보통10점 중 6점

유형
재귀, 분할 정복, 수학
정답자
아직 제출이 없습니다

문제

제3 행성의 어느 별에서는 숫자 3을 매우 좋아한다. 그래서 이 행성의 모든 것은 셋으로 나뉜다.

야텝은 제3 행성의 평범한 주민이다. 당연히 그는 사각형이 아니라 삼각형 집에 산다. 최근 야텝이 심심해졌다. 그래서 0부터 3n3^n까지의 모든 정수를 가져다 세 부분으로 나누었다. 0부터 3n−13^{n-1}까지, 3n−1+13^{n-1}+1부터 2⋅3n−1−12\cdot3^{n-1}-1까지, 그리고 2⋅3n−12\cdot3^{n-1}부터 3n3^n까지다. 그래도 부족해서 첫 번째 부분과 세 번째 부분에도 같은 연산을 적용했다(1과 3은 3의 거듭제곱이니까!). 그는 여기서 멈추지 않았다. 새로 생긴 첫 번째와 세 번째 부분에도 같은 분할을 적용했다. 수 두 개짜리 묶음이 나올 때까지 첫 번째와 세 번째 부분을 계속 나누었다(두 개짜리 묶음은 세 부분으로 나누기가 매우 어렵다). 구체적으로, l부터 r까지의 수 묶음을 나누면 세 묶음이 생긴다. l부터 (2⋅l+r)3\frac{(2 \cdot l + r)}{3}까지, (2⋅l+r)3+1\frac{(2 \cdot l + r)}{3} + 1부터 (l+2⋅r)3−1\frac{(l + 2 \cdot r)}{3} - 1까지, 그리고 (l+2⋅r)3\frac{(l + 2 \cdot r)}{3}부터 r까지다.

n=2n = 2인 경우를 보자. 처음에는 0부터 9까지의 모든 수가 있다. 첫 번째 분할 후에는 0-3, 4-5, 6-9 부분이 생긴다. 다음 분할 후에는 0-1, 2-3, 4-5, 6-7, 8-9가 된다.

야텝은 수를 아무렇게나 나누지 않았다. l부터 r까지의 수 묶음을 세 부분으로 나누기 전마다, l과 r을 사각형이 아닌 삼각형 칸이 그려진 특수한 종이에 적었다. 이미 종이에 있는 수는 다시 적지 않았다. 위 예에서 종이에는 0, 1, 2, 3, 6, 7, 8, 9가 적힌다.

야텝이 작업을 마치자, k번째 행성에서 온 친구 야사브가 찾아왔다. 야사브는 야텝의 종이에 차이가 정확히 kk인 두 수가 있는지 알고 싶어 한다. 야사브와 야텝을 도와 그런 두 수를 찾아라.

입력

첫 줄에 두 정수 nn과 kk가 주어진다 (1≤n≤10001\le n \le 1000, 0≤k≤3n0 \le k \le 3^n).

출력

출력 파일에 aa와 bb를 출력하라. 두 수는 야텝의 종이에 적혀 있어야 하며 b−a=kb - a = k를 만족해야 한다. 그런 쌍이 여러 개이면 그중 아무거나 출력해도 된다. 그런 수가 없으면 <<Impossible>>이라는 단어 하나만 출력한다.

예제2

  1. 예제 1

    입력
    2 2
    
    예상 출력
    1 3
    
  2. 예제 2

    입력
    2 5
    
    예상 출력
    3 8