← 返回题目列表

Codeforces · 768/C

C. 琼恩·雪诺和他最喜欢的号码

中文机器翻译题面 查看原题

琼恩·雪诺现在必须与异鬼战斗。他有n个游侠,每个游侠都有自己的实力。琼恩·雪诺也有他最喜欢的数字 x。每个游侠只有在异鬼的力量等于他的力量时才能与异鬼战斗。然而,他认为他的护林员很弱,需要改进。乔恩现在认为,如果他将一些游骑兵的强度与他最喜欢的数字 x 进行按位异或,他可能会得到高强度的士兵。于是,他决定执行以下操作k次:

1.将所有游侠按照实力递增的顺序排成一条直线。
2. 将每个备用游侠的强度与 x 进行按位异或(写为 $$\bigcirc$$)并更新其强度。

1. 第一游侠的强度更新为 $$5 \oplus 2$$,即 7。
2.第二个游侠的强度保持不变,即7。
3. 第三游侠的强度更新为$$9 \oplus 2$$,即11。
4. 第四个游侠的强度保持不变,即 11。
5.第五游侠的强度更新为$$15 \oplus 2$$,即13。

现在,Jon 想知道执行上述操作 k 次后游骑兵的最大和最小力量。他需要你帮助完成这项任务。你能帮助他吗?

输入

第一行由三个整数 n, k, x (1 ≤ n ≤ 105, 0 ≤ k ≤ 105, 0 ≤ x ≤ 103) — Jon 拥有的游骑兵数量、Jon 执行操作的次数以及 Jon 最喜欢的数字组成。

第二行由 n 个整数组成,代表游侠 a1, a2, ..., an (0 ≤ ai ≤ 103) 的强度。

输出

输出两个整数,执行k次操作后游侠的最大和最小强度。

示例

输入 #1

5 1 2
9 7 11 15 5

输出 #1

13 7

输入 #2

2 100000 569
605 986

输出 #2

986 605