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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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)