아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Нет Пети

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

요약
구간 [0, 3^n]을 재귀적으로 삼등분하며 끝점을 모은 뒤, 저장된 두 수의 차가 정확히 k인 쌍을 찾는다.
난이도

보통10점 중 7점

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

문제

На третьей планете одной звезды очень любят цифру три. Именно по этой причине все на этой планете делят на три части.

Ятеп --- простой житель третьей планеты. Естественно он живет не в квадратном, а в треугольном доме. Недавно Ятеп заскучал, и, чтобы как-нибудь себя развлечь, он взял все целые числа от 00 до 3n3^n и разделил их на три части: от 00 до 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. Но этого ему показалось мало, поэтому он применил такую же операцию к первой и третьей частям (ведь 11 и 33 --- степени тройки!). Но и на этом простой житель третьей планеты не остановился. Он применил свое разбиение к новым первым и третьим частям. Он продолжал делить первые и третьи части, пока у него не стали получаться наборы из двух чисел (их очень сложно делить на три части). Более конкретно, если Ятеп делит набор чисел от ll до rr, то получает три набора: от ll до (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} до rr.

Рассмотрим деятельность Ятепа на примере n=2n = 2. В начале имеются все числа от 00 до 99. После первого разбиения получаем части 0−30-3, 4−54-5, 6−96-9. После следующего разбиения 0−10-1, 2−32-3, 4−54-5, 6−76-7 и 8−98-9.

Но Ятеп не просто так делил все числа. Каждый раз перед тем как разделить набор чисел от ll до rr на три части он выписывал числа ll и rr на специальный треугольный листочек в треугольную, а не квадратную клеточку. При этом, если число уже было на листочке, то Ятеп его не выписывал. В описанном выше примере на листочке возникнут числа 00, 11, 22, 33, 66, 77, 88, 99.

Как только Ятеп закончил свою работу, к нему в гости зашел Ясав --- Ятепин друг с kk-ой планеты. Ясава очень интересуют, есть ли на Ятепином листочке два числа с разницей ровно 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