Given an integer n such that n is divisible by 4, find an integer x satisfying:

• n ≤ x < 2n
• x has the same bit-length as n

Define:

v = n ⊕ (n + 1) ⊕ (n + 2) ⊕ ... ⊕ x

where ⊕ denotes the bitwise XOR operation.

Your task is to choose x such that v is maximum.

If multiple values of x produce the same maximum value of v, return the smallest such x.

Examples

Example 1

For n = 4:

4 ⊕ 5 ⊕ 6 = 7

The maximum is achieved at:

x = 6

Example 2

For n = 8:

8 ⊕ 9 ⊕ ... ⊕ 14

The optimal value of x is:

14

Constraints

4 ≤ n ≤ 10¹²

n is divisible by 4

n ≤ x < 2n

x must have the same bit-length as n


Output

Return the value of x that maximizes:

n ⊕ (n + 1) ⊕ ... ⊕ x

If multiple values are optimal, return the smallest x.