Double Up 2

Time limit2sMemory limit1024 MB

Summary

Each array element can be doubled mod M. Find the largest number of equal values reachable and the fewest doublings needed to make that many equal.

Level: Medium7 of 10
Topics: Graph, Dynamic programming, Number theory, Hash map
Solved: No attempts yet

Problem

Dalgu has an array $A$ of $N$ integers and an integer $M$ . Dalgu can perform the following operation on this array as many times as he wants.

Choose an index $i$ with $1 \le i \le N$ . Replace $A_i$ with $(A_i \times 2) \bmod M$ .

After Dalgu finishes all operations, let $k$ be the number that appears most often in the array. Find the maximum possible number of occurrences of $k$ , and the minimum number of operations needed to reach an array state where this maximum is achieved.

Input

The first line contains $N$ and $M$ , separated by a space. ( $1 \le N, M \le 1\,000\,000$ )

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ , separated by spaces. ( $0 \le A_i < M$ )

Output

Print the maximum possible number of occurrences of the most frequent value, and the minimum number of operations needed to reach such an array, separated by a space.

Examples2

Example 1
Input
```
4 7
4 1 1 5
```
Expected output
```
3 1
```

Example 2

Input

20 10
2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7

Expected output

18 33