32692번 - Double Up 2

문제

$N$개의 정수로 이루어진 배열 $A$와 정수 $M$이 주어진다. 달구는 이 배열에 다음 작업을 원하는 만큼 수행할 수 있다.

• 1ドル \le i \le N$을 만족하는 $i$를 고른다. $A_i$를 $\left( A_i \times 2 \right) \bmod{M}$으로 교체한다.

달구가 모든 작업을 수행한 뒤, 배열에서 가장 많이 등장하는 수를 $k$라 하자. $k$의 등장 횟수로 가능한 최댓값을 구하고, 그러한 배열 상태를 만들기 위해 진행해야 하는 연산의 최소 횟수를 구하라.

입력

첫째 줄에 열의 길이 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M\le 1\ 000\ 000)$

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i < M)$

출력

작업을 원하는 만큼 수행한 뒤, 배열에서 가장 많이 등장하는 수의 가능한 최대 등장 횟수와 그런 배열을 만들기 위해 진행해야 하는 연산의 최소 횟수를 공백으로 구분하여 출력한다.

제한

힌트