Creative Accounting

Byteasar and his friends are spending their summer vacation at the well-known Byten-Byten resort. Where there are many tourists, prices are high, so from time to time they took on odd jobs to earn extra money for the trip. Byteasar served as the treasurer for the whole group.

When the vacation ends, the group settles up. The friends decided to split the entire surplus (or debt) evenly among the $m$ people in the group. If it cannot be divided exactly, then as a reward for his work as treasurer Byteasar takes the leftover amount from the common budget so that the remaining amount is divisible by the group size. In particular, if the total is a debt (negative), his reward still increases the debt.

Byteasar's reward is exactly the remainder of the chosen period's total balance $S$ when divided by $m$, where the remainder is always taken as a value between $0$ and $m-1$. In other words, his reward is the unique $r \in [0, m-1]$ such that $S - r$ is a multiple of $m$. For example, if $S = 30$ and $m = 13$, then $30 = 2 \times 13 + 4$, so the reward is $4$; if $S = -1$ and $m = 13$, then $-1 = (-1) \times 13 + 12$, so the reward is $12$.

Byteasar has hatched a sneaky plan. He will show his friends only the part of his ledger covering days $l$ through $r$ ($1 \le l \le r \le n$). He wants to choose this contiguous period so that the reward for its total balance is as large as possible.

Write a program that computes how much money Byteasar will receive as treasurer if he chooses the period optimally.

The first line contains two integers $n$ and $m$ ($1 \le n \le 200\,000$, $2 \le m \le 10^{18}$): the length of the vacation in days and the size of the group (including Byteasar). The second line contains $n$ integers $a_i$ ($|a_i| \le 10^{18}$), where $a_i$ is the financial result of day $i$ (in bythalers); a positive value means the income exceeded the spending.

Print a single integer: the maximum number of bythalers Byteasar can receive for serving as treasurer.