Số dư luân phiên (Streaming Sum Modulo K)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho n số nguyên không âm và số nguyên dương k. Tính phần dư khi chia tổng tất cả n số cho k; chỉ in số dư trong [0,k-1]. Không cần lưu cả dãy, cập nhật số dư sau mỗi số đọc.

Input

Dòng đầu có n k; tiếp theo đúng n số nguyên không âm, cách nhau bởi khoảng trắng hoặc xuống dòng.

Output

In đúng một số nguyên từ 0 đến k−1. Khi n=0, in 0.

Subtask

• Subtask 1 (20%): 0 ≤ n ≤ 20; 1 ≤ k ≤ 100; 0 ≤ a_i ≤ 100.

• Subtask 2 (30%): 0 ≤ n ≤ 1000; 1 ≤ k ≤ 10^6; 0 ≤ a_i ≤ 10^6.

• Subtask 3 (50%): 0 ≤ n ≤ 100000; 1 ≤ k ≤ 10^9; 0 ≤ a_i ≤ 10^9.

Ví dụ

Ví dụ 1

Input:

3 7
6 6 6

Output:

4

Giải thích: Tổng bằng 18, 18 chia 7 dư 4.

Ví dụ 2

Input:

0 1

Output:

0

Giải thích: Tổng rỗng bằng 0 và số dư theo k=1 là 0.