Popcount 与异或

题目描述

给定非负整数 $a$、$b$ 和 $C$。

判断是否存在满足以下全部五个条件的非负整数对 $(X,Y)$。如果存在,输出其中一对。

• $0 \leq X \lt 2^{60}$
• $0 \leq Y \lt 2^{60}$
• $\operatorname{popcount}(X) = a$
• $\operatorname{popcount}(Y) = b$
• $X \oplus Y = C$

其中,$\oplus$ 表示按位异或。

如果存在多对满足条件的 $(X,Y)$,输出任意一对即可。

什么是 popcount?

对于非负整数 $x$,$x$ 的 popcount 是指 $x$ 的二进制表示中 $1$ 的个数。

更准确地说,对于满足 $\displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace)$ 的非负整数 $x$,有 $\displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i$。

例如,$13$ 的二进制表示是 1101,所以 $\operatorname{popcount}(13)=3$。

什么是按位异或?

对于非负整数 $x,y$,按位异或 $x \oplus y$ 定义如下。

在 $x \oplus y$ 的二进制表示中,$2^k\ (k\geq0)$ 这一位为 $1$,当且仅当 $x$ 和 $y$ 的二进制表示中 $2^k\ (k\geq0)$ 这一位恰好有一个为 $1$;否则该位为 $0$。

例如,$9$ 和 $3$ 的二进制表示分别为 1001 和 0011,所以 $9 \oplus 3 = 10$(二进制为 1010)。

输入格式

输入按以下格式从标准输入给出:

$a$ $b$ $C$

输出格式

如果存在满足条件的非负整数对,选择其中一对 $(X,Y)$,以空格分隔按顺序输出 $X$ 和 $Y$。 如果不存在这样的对,输出 -1。

样例

3 4 7

28 27

对 $(X,Y)=(28,27)$ 满足条件。 这里,$X$ 和 $Y$ 的二进制表示分别为 11100 和 11011。

$X$ 的二进制表示是 11100,所以 $\operatorname{popcount}(X)=3$。

$Y$ 的二进制表示是 11011,所以 $\operatorname{popcount}(Y)=4$。

$X \oplus Y$ 的二进制表示是 00111,所以 $X \oplus Y=7$。

如果存在多对满足条件的非负整数对,输出任意一对即可,例如输出 42 45 也会被判定为正确。

34 56 998244353

-1

不存在满足条件的非负整数对。

39 47 530423800524412070

540431255696862041 10008854347644927

注意,要输出的值可能无法放入 $32$ 位整数中。

数据范围

• $0 \leq a \leq 60$
• $0 \leq b \leq 60$
• $0 \leq C \lt 2^{60}$
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。