Cho mảng \(A\) gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) và một số nguyên dương \(k\). Yêu cầu: viết chương trình tìm đoạn con liên tiếp dài nhất có tổng các phần tử chia hết cho \(k\).

Input

• Dòng một chứa hai số nguyên dương \(n, k\):
  • \(1 \le n \le 100\,000\)
  • \(1 \le k \le 1000\)
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\):
  • \(0 \le a_i \le 10^8\), \(\forall i=\overline{1;n}\)
• Các số nguyên trong file dữ liệu được ghi cách nhau ít nhất một dấu cách trống.

Output

• Ghi ra một số nguyên duy nhất là độ dài lớn nhất của đoạn con tìm được.

Example

7 5
7 1 4 3 2 5 9

5

Scoring

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \le 100\);
• \(50\%\) số test tương ứng với \(50\%\) số điểm có \(100 < n \le 10\,000\);
• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(10\,000 < n \le 100\,000\).