$$$A={a_1, a_2, \cdots, a_n }$$$ is a set containing $$$n$$$ natural numbers (non negative integers) (according to the definition of the set, the number of $$$n$$$ is different in two), and the maximum value is less than a given positive integer $$$k$$$. We needs to perform several rounds of merging operations on the numbers in the set $$$A$$$ until there is only one number left in $$$A$$$. The process of each round of consolidation is as follows:

1. Select number pairs $$$(x,y)$$$:

   • Select the two closest numbers $$$x $$$and $$$y $$$from $$$A $$$, that is, $$$|x-y|$$$ is the smallest of all pairs;
   • If multiple number pairs meet the conditions, further select the one with the smallest $$$(x+y)$$$;
   • Considering the difference between two numbers in $$$A$$$ , the unique number pair $$$(x,y)$$$ can be selected according to the above requirements (that is, $$$| x - y |$$$ is the first keyword, and $$$(x+y)$$$ is the second keyword).

2. Merge $$$x$$$ and $$$y$$$ into $$$z$$$: $$$z=(x+y)mod k$$$

   • Specifically, first delete $$$x$$$ and $$$y$$$ from the set $$$A$$$; If the set $$$A$$$ does not contain $$$z$$$, add $$$z$$$back to the set $$$A$$$.This ensures that the natural numbers in $$$A$$$ are always different and less than $$$k$$$.

We need to know the total number of merge operations and the remaining number in $$$A$$$ after all merge operations are completed. All the data satisdies

Input

$n\le10^5$、$k \le 10^8$， $a_i$（$1 \le i \le n$） $0 \le a_i < k$。