Migrated from Lutece 1560 Icerain

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There will be $m$ persons to hold a wedding ceremony. As a nice girl, icerain want to choose at least one gift for each person.

There are $n$ gifts in a shop, the ith has a value $w_i$. When icerain is confusing how to select the gifts, a magician said to her that "after you choosing the gifts, you can choose an integer $x$ in the rang of $[0, 2^{30} - 1]$, and I can change the values of the gifts you chosen from $w_i$ to $w_i$ $\oplus$ $x$", "$\oplus$" means bitwise xor operation.

How lovely she is, but icerain is more confused about how to select the gifts and choose the number $x$. Can you help her to choose at least $m$ gifts and the number $x$ such that the average value of the gifts you chosen is as large as possible.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers $w_1, w_2, ..., w_n$.

$1 \leq m \leq 20$, $m \leq n \leq 10000$, $0 \leq w_i \leq 2^{30}-1$.

Output

The maximum average value in the form of irreducible fraction.

Samples

4 2
1 1 1 1

1073741823/1

Resources

The 15th UESTC Programming Contest Preliminary