Warm-up Equation

The brain is also a muscle, and it cannot be used without a warm-up, so we offer you a warm-up task (even without any legend).

You are given three integers $a$, $b$ and $g$, and the equation system:

Here, $|$ means bitwise OR operation.

Firstly, you need to calculate the number of non negative roots for this equation system. In other words, you need to find the number of distinct pairs $(\alpha ,\beta )$, such that $\alpha +\beta =a$ and $\alpha |\beta =b$. Please note that $(\alpha ,\beta )$ and $(\beta ,\alpha )$ are considered as distinct pairs (if $\alpha \ne \beta$).

Secondly, you need to find the smallest possible distance between $x$ and $y$ (i.e., the smallest possible value of $|\alpha -\beta |$ among all the roots) or $-1$ if there are no roots.

If $g=0$, then you have to output just the first answer. Otherwise, you need to output both answers.

Input

The first and only line contains three integers $a,b,g$ $(1\le a,b\le 10^{18},0\le g\le 1).$

Output

In the first line, output the number of positive roots for this equation system.

If $g=1$, then in the second line output the smallest distance between $x$ and $y$, or $-1$ if no solution exists. Otherwise, do not output anything in the second line.

Examples

Scoring

1. ($8$ points): $a<b$;

2. ($8$ points): $a\le 10^3,g=0$;

3. ($4$ points): $a\le 10^3$;

4. ($11$ points): $a\le 10^6,g=0$;

5. ($5$ points): $a\le 10^6$;

6. ($25$ points): $a\le 10^{18},g=0$;

7. ($14$ points): no additional constraints.