Password

Time limit1sMemory limit128 MB

Summary

Given integer A, find the nearest smaller and nearest larger integers with the same popcount as A, using bit manipulation, or print 0 if none exists.

Level: Medium4 of 10
Topics: Bit manipulation, Math, Greedy
Solved: No attempts yet

Problem

A security company wants to make two integers for a password from one positive integer A.

Let x be the number of 1 bits in the binary representation of A. Find the following two integers.

The closest integer smaller than A whose binary representation has exactly x one bits
The closest integer greater than A whose binary representation has exactly x one bits

Write a program that finds and prints these two integers.

Input

The first line contains one positive integer A.

1 <= A <= 10^18

Output

Print two integers separated by a space: first the closest smaller integer satisfying the condition, then the closest greater integer satisfying the condition.

If no such integer exists on one side, print 0 in that position.

Examples2

Example 1
Input
```
43
```
Expected output
```
39 45
```
Example 2
Input
```
7
```
Expected output
```
0 11
```