Description

Given a sequence $a_1, a_2, \cdots, a_n$ and $k, p$.

Let $S_{i,j}=\sum\limits_{k=i}^j a_k$, then:

$$\mathit{Answer}=\min\{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}$$

where $i \le j$, and $\{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}\ne\varnothing$.

Input Format

The first line contains three positive integers $n, k, p$.

The second line contains $n$ positive integers, denoting $a_1, a_2, \cdots, a_n$.

Output Format

Output one positive integer on a single line, which is $\mathit{Answer}$.

7 2 17
12
13
15
11
16
26
11

2

Hint

Constraints

For $100\%$ of the testdata, $1\le n\le10^5$, $1\le k,p,a_i\le10^{18}$.

Translated by ChatGPT 5