题目内容

你有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。你可以对此序列执行任意次（包括零次）操作。每次操作会选定一个下标 $i$（$1 \le i \le n$）和一个非负整数 $y$（$0 \le y \le M$），将 $a_i$ 更新为 $a_i \oplus y$（其中 $\oplus$ 表示按位异或运算），同时消耗 $y$ 单位的代价。多次操作的代价累加。

完成所有操作后，定义序列的总异或和为所有无序下标对的异或值之和：

你的目标是让该总异或和尽可能大。在总异或和达到最大的前提下，总代价应尽可能小。请你求出能够获得的最大总异或和，以及对应的最小总代价。

序列长度 $n$ 满足 $2 \le n \le 10^5$；操作中 $y$ 的上限 $M$ 满足 $1 \le M < 2^{30}$；所有初始 $a_i$ 满足 $0 \le a_i < 2^{30}$；所有数值均为整数。

输入描述

第一行包含两个整数 $n$ 和 $M$，分别表示序列长度和操作中 $y$ 的最大允许值。第二行包含 $n$ 个整数，依次表示初始序列 $a_1, a_2, \dots, a_n$。

输出描述

输出一行两个整数，第一个整数表示能获得的最大总异或和，第二个整数表示达到该总异或和所需的最小总代价。

样例1

输入

3 3
0 0 0

输出

6 3

说明

序列长度 $n=3$，操作上限 $M=3$。不超过 $M$ 的最大 $2$ 的幂为 $p=2$，对应的低位个数 low_bits=2，即第 0、1 位可以任意修改。

对于每一个可变位，当 $1$ 的个数取 $\lfloor n/2 \rfloor = 1$ 或 $\lceil n/2 \rceil = 2$ 时对答案的贡献最大，最大贡献均为 $1 \times 2 \times 2^b$。第 0 位贡献 2，第 1 位贡献 4，最大异或和为 6。初始元素全为 0，各位 $1$ 的个数均为 0。为达到最优，第 0 位需要翻转 1 次，代价 $1$；第 1 位需要翻转 1 次，代价 $2$；总代价为 3。实际操作可以对一个 $a_i$ 异或 $3$（先异或 $p=2$ 再异或 $1$，每步均 $\le M$），使得序列变为 [0,0,3]，异或和为 6。

样例2

输入

4 6
1 2 3 4

输出

28 4

说明

$n=4$，$M=6$。最大 $2$ 的幂 $p=4$，可操作的低位为第 0、1、2 位。$n$ 为偶数时，每个可变位必须恰好有 $n/2 = 2$ 个 $1$ 才能达到最大贡献 $2 \times 2 \times 2^b$。

初始序列为 [1,2,3,4]，二进制分别为 001、010、011、100。统计各低位：第 0 位 $cnt=2$，第 1 位 $cnt=2$，第 2 位 $cnt=1$。高位不可变且均为 0。第 0、1 位已达到目标，第 2 位距离目标差 1 个 $1$，翻转 1 次的代价为 $1 \times 2^2 = 4$。最大异或和为 $2\times2\times(1 + 2 + 4) = 28$，最小代价为 4。例如将 $a_1=1$ 异或 $4$ 变为 $5$，序列变为 [5,2,3,4]，总异或和达到 28。

样例3

输入

2 1
2 3

输出

1 0

说明

$n=2$，$M=1$。此时 $p=1$，可操作的低位仅有第 0 位。偶数长度要求第 0 位最终有 $1$ 个 $1$。

初始 $a_1=2$（二进制 10），$a_2=3$（二进制 11），第 0 位的 $cnt=1$，已经满足要求，无需任何操作，代价为 0。第 1 及更高位不可修改，当前第 1 位有两个 $1$，贡献为 $2 \times 0 \times 2^1 = 0$。最大异或和仅来自第 0 位：$1 \times 1 \times 1 = 1$，与初始异或和 $2 \oplus 3 = 1$ 一致。

样例4

输入

5 10
7 7 7 7 7

输出

90 30

说明

$n=5$，$M=10$，$p=8$，可变的低位为第 0~3 位。$n$ 为奇数时，每个可变位 $1$ 的个数可以取 $\lfloor n/2 \rfloor = 2$ 或 $\lceil n/2 \rceil = 3$，最大贡献均为 $2 \times 3 \times 2^b = 6 \times 2^b$。

初始 $5$ 个数全是 $7$（二进制 0111），因此第 0、1、2 位的 $cnt=5$，第 3 位 $cnt=0$。为最小化翻转次数：第 0、1、2 位选择目标 $3$（离 $5$ 更近，翻转 $2$ 次），第 3 位选择目标 $2$（翻转 $2$ 次）。总代价为 $2 \times (2^0 + 2^1 + 2^2 + 2^3) = 30$。最大异或和为 $6 \times (1+2+4+8) = 90$。

操作方法：保留三个 $7$ 不变，将另外两个 $7$ 变为 $8$。单个 $7$ 变为 $8$ 需异或 $15$，可分两步：先异或 $8$（$\le M$）再异或 $7$（$\le M$），总代价 $15$。最终序列为三个 $7$ 和两个 $8$，第 0~2 位各 $3$ 个 $1$，第 3 位 $2$ 个 $1$，异或和达到 $90$，总代价 $30$。