Under construction

Still being built. Things may change

No Petya

Time limit2sMemory limit1024 MB

Summary
Given n and k, find two numbers on Yatep's sheet whose difference is exactly k, or report that no such pair exists.
Level

Medium6 of 10

Topics
Recursion, Divide and conquer, Math
Solved
No attempts yet

Statement

On the third planet of one star, people are very fond of the number three. For this reason, everything on this planet is divided into three parts.

Yatep is an ordinary resident of the third planet. Naturally, he lives in a triangular house, not a square one. Recently Yatep got bored, so to entertain himself he took all integers from 00 to 3n3^n and split them into three parts: from 00 to 3n−13^{n-1}, from 3n−1+13^{n-1}+1 to 2⋅3n−1−12\cdot3^{n-1}-1, and from 2⋅3n−12\cdot3^{n-1} to 3n3^n. That seemed too little, so he applied the same operation to the first and third parts (after all, 11 and 33 are powers of three!). He did not stop there. He applied his split to the new first and third parts, and kept splitting the first and third parts until he got sets of two numbers (those are hard to split into three parts). More precisely, if Yatep splits a set of numbers from ll to rr, he gets three sets: from ll to (2⋅l+r)3\frac{(2 \cdot l + r)}{3}, from (2⋅l+r)3+1\frac{(2 \cdot l + r)}{3} + 1 to (l+2⋅r)3−1\frac{(l + 2 \cdot r)}{3} - 1, and from (l+2⋅r)3\frac{(l + 2 \cdot r)}{3} to rr.

Consider Yatep's work for n=2n = 2. At the start, all numbers from 00 to 99 are present. After the first split we get the parts 0−30-3, 4−54-5, 6−96-9. After the next split we get 0−10-1, 2−32-3, 4−54-5, 6−76-7, and 8−98-9.

Yatep did not split the numbers at random. Each time before splitting a set of numbers from ll to rr into three parts, he wrote the numbers ll and rr on a special sheet of paper with triangular cells instead of square ones. If a number was already on the sheet, he did not write it again. In the example above, the sheet ends up with the numbers 00, 11, 22, 33, 66, 77, 88, 99.

When Yatep finished his work, his friend Yasav, from the kk-th planet, came to visit. Yasav wants to know whether Yatep's sheet contains two numbers whose difference is exactly kk. Help Yasav and Yatep find these numbers.

Input

The first line contains two integers nn and kk (1≤n≤10001\le n \le 1000, 0≤k≤3n0 \le k \le 3^n).

Output

Print the numbers aa and bb such that both are on Yatep's sheet and b−a=kb - a = k. If there are several such pairs, print any of them. If no such numbers exist, print the single word <<Impossible>>.

Examples2

  1. Example 1

    Input
    2 2
    
    Expected output
    1 3
    
  2. Example 2

    Input
    2 5
    
    Expected output
    3 8