解题思路

设 $p$ 为不超过 $k$ 的最大 $2$ 的幂，即 $p=2^m$，则 $p\le k<2p$。

一次操作可以让某个 $a_i$ 异或上一个 $x$，其中 $0\le x\le k$。多次操作等价于让 $a_i$ 异或上若干个 $x$ 的异或值。

由于 $0,1,\dots,k$ 中一定包含 $0,1,\dots,p-1$ 和 $p$，所以对于任意 $0\le y<2p$：

• 若 $y\le k$，可以直接操作一次，代价为 $y$；

题目内容

给定一个长度为 $n$ 的数组 $a$，以及一个整数 $k$。你可以对数组执行任意次（可以为零次）以下操作：

• 选择一个下标 $i$ 以及一个整数 $x$，满足 $0 \le x \le k$，并将 $a_i$ 赋值为 $a_i \oplus x$，其中 $\oplus$ 代表按位异或。该操作的代价为 $x$。

一个操作序列的总代价为其所有操作的代价之和。 你需要最大化所有操作之后下面式子的值：

如果有多种可能的操作序列使上式的值最大化，你需要选择总代价最小的那个。为了方便，你只需要输出上式的最大值，以及最小的总代价。

输入描述

第一行输入两个整数 $n, k$（$2 \le n \le 10^5,\ 1 \le k < 2^{30}$），分别表示 $a$ 的长度，以及操作时 $x$ 的上限。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{30}$），代表 $a$ 中的元素。

输出描述

输出一行两个整数。第一个整数代表上式的最大值；第二个整数代表最小的总代价。

样例1

输入

3 3
0 1 9

输出

22 2

说明

我们可以对数组进行一次操作：选择 $i=2$ 和 $x=2$，将 $a_2$ 赋值为 $a_2 \oplus 2 = 1 \oplus 2 = 3$。操作代价为 $2$。此时，数组 $a$ 变为 $\{0, 3, 9\}$。

操作后上式的和为：

可以证明，$22$ 是可得到的最大值，且最小的总代价为 $2$。

样例2

输入

5 109
114 514 19 19 810

输出

4858 84