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

Difficulty: interview

Starter code:

Solutions:
t=1
for _ in range(t):
    n,m,k=(list(map(int,input().split())))
    a=list(map(int,input().split()))
    for i in range(n):
        a[i]=a[i]%k
    
    s=1
    for j in range(k):
        ss=0
        v=0
        for i in range(n):
            v+=min(abs(a[i]-j),k-abs(a[i]-j))
            while ss<i and v>m:
                v-=min(abs(a[ss]-j),k-abs(a[ss]-j))
                ss+=1
            s=max(s,i-ss+1)
        
    print(s)