X and K

Interview

Time limit2sMemory limit128 MB

Summary

Given X and K, find the K-th smallest positive integer Y such that X+Y equals X OR Y, which requires placing K's bits into the zero-bit positions of X.

Level: Medium5 of 10
Topics: Bit manipulation, Math, Implementation
Solved: No attempts yet

Problem

You are given two positive integers X and K. List all positive integers Y that satisfy the following equation in increasing order, and find the K-th smallest such Y.

X + Y = X | Y

Here, | denotes the bitwise OR operation.

Input

The first line contains two positive integers X and K, separated by a space.

Each of X and K is at most 2,000,000,000.

Output

Print the K-th smallest positive integer Y satisfying X + Y = X | Y.

The answer may be greater than 2^31 - 1.

Examples4

Example 1
Input
```
5 1
```
Expected output
```
2
```
Example 2
Input
```
5 5
```
Expected output
```
18
```
Example 3
Input
```
10 3
```
Expected output
```
5
```
Example 4
Input
```
1 1000000000
```
Expected output
```
2000000000
```