Uppal-balu is busy in extraction of gold from ores. He got an assignment from his favorite professor MH sir, but he got stuck in a problem. Can you help Uppal-balu to solve the problem.
You are given an array $a_1$, $a_2$, $\dots$, $a_n$ of length $n$. You can perform the following operations on it:
- Choose an index $i$ ($1 \leq i \leq n$), and replace $a_i$ by $a_{i} + 1$ or $a_{i} - 1$, which means add or subtract one to the element at index $i$.
Beauty of the array is defined as maximum length of a subarray containing numbers which give same remainder upon dividing it by $k$ (that is, ($a_l$ mod $k$) = ($a_{l+1}$ mod $k$) = $\dots$ = ($a_r$ mod $k$) for some $1 \leq l \leq r \leq n$).
You need to calculate the beauty of the array $a_1$, $a_2$, $\dots$, $a_n$ after applying at most $m$ operations.
NOTE:
- The subarray of a is a contiguous part of the array $a$, i. e. the array $a_l$, $a_{l+1}$, $\dots$, $a_r$ for some $1 \leq l \leq r \leq n$.
- $x$ mod $y$ means the remainder of $x$ after dividing it by $y$.

-----Input:-----
- First line of input contains 3 integers $n$, $m$ and $k$.
- The second line contains $n$ integers $a_1$, $a_2$, $\dots$, $a_n$.

-----Output:-----
Output in a single line the beauty of the array after applying at most m operations.

-----Constraints-----
- $1 \leq n,m \leq 2\cdot10^{5}$
- $1 \leq k \leq 7$
- $1 \leq a_i \leq 10^9$

-----Sample Input 1:-----
7 3 4

8 2 3 7 8 1 1

-----Sample Output 1:-----
5

-----Sample Input 2:-----
8 3 5

7 2 1 3 6 5 6 2

-----Sample Output 2:-----
5

见题面

见题面