Hôm nay algorit và bin9638, \(2\) nam thần của làng K-pop đang đi chơi với nhau. May mắn thay họ gặp 1 cô em gái xinh đẹp tên là Jennie. Jennie vốn đã hâm mộ \(2\) người từ lâu nên đã đố họ \(1\) bài toán. Ai giải ra trươc là sẽ là người được đi chơi, hẹn hò với Jennie.

Bài toán là cho 1 dãy số nguyên dương \(A_1, A_2,…,A_n (n≤10^6, A_i≤10^9)\). 1 dãy con liên tiếp không rỗng của \(A\) được xem là dãy “ngu ngốc“ khi tổng phần tử của dãy con đó chia hết cho số nguyên dương \(k (1≤ k ≤10^6)\). Jennie đố algorit và bin9638 hãy tìm cách chia dãy \(A\) thành \(2\) dãy con “ngu ngốc” không giao nhau sao cho tổng độ dài \(2\) dãy là lớn nhất. bin9638 rất muốn được hẹn hò với Jennie nhưng vì mải ngắm nhìn nhan sắc tuyệt trần của cô nên anh không có tâm trí nào mà giải toán nữa. Bạn hãy giúp bin9638 nhé !

Yêu cầu:

• Hãy tìm tổng độ dài lớn nhất.

Input:

• Dòng đầu tiền lần lượt là \(n\) và \(k\), dòng thứ \(2\) là các số \(A_i\).

Output:

• \(1\) số duy nhất là kết quả, nếu không có cách chia thì in ra \(0\).

Scoring:

• Subtask \(1\) (\(50\%\) số điểm): có \(n≤10^4\).

• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example:

3 2
1 2 3

0

4 2
1 2 3 4

4