题目描述

你需要在$[0,2^n)$中选一个整数$x$，接着把$x$依次异或$m$个整数$a_1\sim a_m$。 在你选出$x$后，你的对手需要选择恰好一个时刻（刚选完数时、异或一些数后或是最后），将$x$变为$(\lfloor\frac{2x}{2^n}\rfloor +2x) \bmod 2^n$ 。 你想使$x$最后尽量大，而你的对手会使$x$最后尽量小。 你需要求出$x$最后的最大值，以及得到最大值的初值数量。

输入

第一行两个整数$n,m$。第二行$m$个整数$a_1\sim a_m$。

输出

第一行输出一个整数，表示$x$最后的最大值。 第二行输出一个整数，表示得到最大值的初值数量。

输入样例

2 3 
1 2 3

输出样例

1 
2

提示

【样例解释】 $x=0$时得到$0$，$x=1$时得到$1$，$x=2$ 时得到$1$，$x=3$时得到$0$。 【数据规模】 对于20%的数据，$n≤10，m≤100$。 对于40%的数据，$n≤10，m≤1000$。 对于另外20%的数据，$n≤30，m≤10$。 对于100%的数据, n≤30，m≤100000，0≤a_i<2^n。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。