Background

Description

你需要在[0,2^n)中选一个整数 x，接着把 x 依次异或 m 个整数a1~am。
在你选出 x 后，你的对手需要选择恰好一个时刻（刚选完数时、异或一些数后或是最后），将 x 变为(⌊2𝑥 2𝑛 ⌋ + 2𝑥)mod 2𝑛。
你想使 x 最后尽量大，而你的对手会使 x 最后尽量小。
你需要求出 x 最后的最大值，以及得到最大值的初值数量。

Format

Input

第一行两个整数 n,m。第二行 m 个整数 a1~am

Output

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

Sample

Input

2 3
1 2 3

Output

1
2

Explanation

x=0 时得到 0，x=1 时得到 1，x=2 时得到 1，x=3 时得到 0。

Limitation

对于 20%的数据，n<=10，m<=100。
对于 40%的数据，n<=10，m<=1000。
对于另外 20%的数据，n<=30，m<=10。
对于 100%的数据 n<=30，m<=100000，0<=ai<2^n。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST