You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b₁, b₂, ..., b_k (1 ≤ b₁ < b₂ < ... < b_k ≤ n) in such a way that the value of $\text{[math]}$ is maximized. Chosen sequence can be empty.

Print the maximum possible value of $\text{[math]}$ .

Input

The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10⁹).

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output

Print the maximum possible value of $\text{[math]}$ .

Note

In the first example you can choose a sequence b = {1, 2}, so the sum $\text{[math]}$ is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {3}.

Maximum Subsequence

Examples