Giải bài trực tuyến

Cho một dãy gồm N (1 ≤ N ≤ 100000) số nguyên dương a₁, a₂, ..., a_n. Tổng a_i + a_i+1 + ... + a_j (1 ≤ i ≤ j ≤ N) được gọi là tổng bộ phận từ i đến j của dãy số.

Cho hai số nguyên dương P và K (1 < P ≤ 10⁹, 0 ≤ K < P). Hãy tìm tổng bộ phận theo modulo P nhỏ nhất không bé hơn K.

Ví dụ, xét dãy số sau:

12     13     15     11     16     26     11

Ở đây N=7, giả sử K=2 và P=17, ta có kết quả là 2 vì 11 + 16 + 26 = 53 và 53 mod 17 = 2. Nếu K=0 ta có kết quả bằng 0 vì 15 + 11 + 16 + 26 = 68 và 68 mod 17 = 0.

Dữ liệu

• Dòng 1: N, K, P.
• Dòng 2..n+1: a₁, a₂,... , a_N, mỗi số trên một dòng.

Kết quả

In ra tổng bộ phận theo modulo P nhỏ nhất không bé hơn K.

Ví dụ

Dữ liệu
7 2 17
12
13
15
11
16
26
11

Kết quả
2