Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks.

Heidi is presented with a screen that shows her a sequence of integers A and a positive integer p. She knows that the encryption code is a single number S, which is defined as follows:

Define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given an integer p. She needs to split A into 2 parts such that:   Each part contains at least 1 element of A, and each part consists of contiguous elements of A.  The two parts do not overlap.  The total sum S of the scores of those two parts is maximized. This is the encryption code. 

Output the sum S, which is the encryption code.


-----Input-----

The first line of the input contains two space-separated integer N and p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – the number of elements in A, and the modulo for computing scores, respectively.

The second line contains N space-separated integers which are the elements of A. Each integer is from the interval [1, 1 000 000].


-----Output-----

Output the number S as described in the problem statement.


-----Examples-----
Input
4 10
3 4 7 2

Output
16

Input
10 12
16 3 24 13 9 8 7 5 12 12

Output
13



-----Note-----

In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of $(3 + 4 \operatorname{mod} 10) +(7 + 2 \operatorname{mod} 10) = 16$.

In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is $(16 + 3 + 24 \operatorname{mod} 12) +(13 + 9 + 8 + 7 + 5 + 12 + 12 \operatorname{mod} 12) = 7 + 6 = 13$.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(N)

Starter code:

Solutions:
(n, p) = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
mx = 0
t = 0
for i in range(n - 1):
	t += a[i]
	x = t % p + (s - t) % p
	mx = max(mx, x)
print(mx)


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
resp = -1
aux = 0
tot = sum(a)
for x in a:
	aux += x
	resp = max(resp, aux % p + (tot - aux) % p)
print(resp)


import math

def func(n, k, a):
	s = sum(a)
	ms = 0
	x = 0
	for i in range(n):
		cs = x % k + s % k
		x += a[i]
		s -= a[i]
		ms = max(ms, cs)
	return ms
for _ in range(1):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(func(n, k, a))


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
sum1 = 0
pre = []
for i in range(n):
	sum1 += a[i]
	sum1 = sum1 % p
	pre.append(sum1)
post = [0 for i in range(n)]
sum1 = 0
for i in range(n - 1, -1, -1):
	post[i] = sum1
	sum1 += a[i]
	sum1 = sum1 % p
s = 0
for i in range(n):
	s = max(pre[i] + post[i], s)
print(s)


(n, p) = map(int, input().split())
v = [int(i) for i in input().split()]
v2 = [v[0]]
for i in range(0, n - 1):
	v2.append(v2[i] + v[i + 1])
max = 0
for i in range(n):
	if v2[i] % p + (v2[n - 1] - v2[i]) % p > max:
		max = v2[i] % p + (v2[n - 1] - v2[i]) % p
print(max)


(N, P) = map(int, input().split())
src = list(map(int, input().split()))
K = sum(src) % P
ans = tmp = 0
for a in src:
	tmp += a
	tmp %= P
	ans = max(ans, tmp + (K - tmp) % P)
print(ans)


import math

def solve(n, P, A):
	score1 = A[0] % P
	score2 = sum(A[1:]) % P
	MAX = score1 + score2
	for i in range(1, n - 1):
		delta = A[i] % P
		score1 = score1 + delta
		if score1 >= P:
			score1 = score1 - P
		score2 = score2 - delta
		if score2 < 0:
			score2 = score2 + P
		score = score1 + score2
		if score > MAX:
			MAX = score
	return MAX
n = [int(i) for i in input().split()]
P = n[1]
n = n[0]
A = [int(i) for i in input().split()]
print(solve(n, P, A))


(n, p) = map(int, input().split())
seq = list(map(int, input().split()))
del1 = 0
del2 = 0
record = 0
seqSum = sum(seq)
lst = []
lst = []
for i in range(n):
	del1 += seq[i]
	del2 = seqSum - del1
	lst.append(del1 % p + del2 % p)
print(max(lst))


(N, p) = map(int, input().split())
A = list(map(int, input().split()))
R = 0
B = []
Sx = 0
Sy = sum(A)
for i in range(0, N - 1):
	Sx += A[i]
	Sy -= A[i]
	Sx = Sx % p
	Sy = Sy % p
	if R < Sx + Sy:
		R = Sx + Sy
print(R)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
minimum = 0
suma = 0
sumb = sum(l)
for j in range(0, n):
	suma += l[j]
	sumb -= l[j]
	value = suma % k + sumb % k
	if value > minimum:
		minimum = value
print(minimum)


(n, p) = list(map(int, input().split()))
arr = list(map(int, input().split()))
sum_ = sum(arr)
res = 0
temp = 0
for i in arr:
	temp += i
	sum_ -= i
	res = max(res, temp % p + sum_ % p)
print(res)


from itertools import accumulate
(N, p) = list(map(int, input().split()))
A = list(map(int, input().split()))
left = [0] + list(accumulate(A))
right = list(accumulate(A[::-1]))[::-1] + [0]
ans = [left[i] % p + right[i] % p for i in range(N + 1)]
print(max(ans))


(a, b) = map(int, input().split())
z = []
p = 0
for i in map(int, input().split()):
	p = (p + i) % b
	z += [p]
p += b
print(max((z[i] + (p - z[i]) % b for i in range(a - 1))))


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
t = 0
k = 0
for i in range(n):
	k += a[i]
s = 0
for i in range(0, n - 1):
	s += a[i]
	t = max(t, s % p + (k - s) % p)
print(t)


(n, k) = map(int, input().strip().split(' '))
lst = list(map(int, input().strip().split(' ')))
s = sum(lst)
s2 = 0
m = s % k
for i in range(n - 1):
	s2 += lst[i]
	s -= lst[i]
	if s2 % k + s % k > m:
		m = s2 % k + s % k
print(m)


(m, n) = list(map(int, input().split()))
l = list(map(int, input().split()))
a = [0] * m
(a[0], ma) = (l[0], 0)
for i in range(1, m):
	a[i] = a[i - 1] + l[i]
for i in range(m):
	if a[i] % n + (a[m - 1] - a[i]) % n > ma:
		ma = a[i] % n + (a[m - 1] - a[i]) % n
print(ma)


(n, p) = map(int, input().split())
a = input().split()
b = []
sum1 = 0
for i in range(n):
	sum1 += int(a[i])
	b.append(sum1)
c = []
for i in range(n):
	c.append(b[i] % p + (sum1 - b[i]) % p)
print(max(c))


(n, p) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
(s1, s2) = (a[0], sum(a) - a[0])
ans = s1 % p + s2 % p
for i in range(n - 1):
	s1 = (s1 + a[i]) % p
	s2 = (s2 - a[i]) % p
	ans = max(ans, s1 + s2)
print(ans)


def main():
	(n, p) = map(int, input().split())
	a = [int(x) for x in input().split()]
	prefix = [a[0]]
	for i in range(1, n):
		prefix.append(prefix[-1] + a[i])
	max_sum = -1
	for i in range(n - 1):
		temp = prefix[i] % p + (prefix[n - 1] - prefix[i]) % p
		if max_sum == -1:
			max_sum = temp
		elif max_sum < temp:
			max_sum = temp
	print(max_sum)
main()


(n, P) = map(int, input().split())
a = list(map(lambda x: int(x) % P, input().split()))
pre = a[0]
suf = sum(a[1:]) % P
num = pre + suf
for i in range(1, n - 1):
	pre += a[i]
	pre %= P
	suf -= a[i]
	if suf < 0:
		suf += P
	num = max(num, pre + suf)
print(num)


s = input().split()
(n, p) = (int(s[0]), int(s[1]))
cl = list(map(int, input().split()))
mx = 0
sm = sum(cl)
qs = cl[0]
for i in range(1, n):
	y = qs % p + (sm - qs) % p
	if y > mx:
		mx = y
	qs += cl[i]
print(mx)


from collections import deque as de
import math
import re
from collections import Counter as cnt
from functools import reduce
from typing import MutableMapping
from itertools import groupby as gb
from fractions import Fraction as fr
from bisect import bisect_left as bl, bisect_right as br

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binarytodecimal(n):
	return int(n, 2)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def getProduct(n):
	product = 1
	while n != 0:
		product = product * (n % 10)
		n = n // 10
	return product

def dupconscount(nums):
	element = []
	freque = []
	if not nums:
		return element
	running_count = 1
	for i in range(len(nums) - 1):
		if nums[i] == nums[i + 1]:
			running_count += 1
		else:
			freque.append(running_count)
			element.append(nums[i])
			running_count = 1
	freque.append(running_count)
	element.append(nums[i + 1])
	return (element, freque)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def ceildiv(x, y):
	return (x + y - 1) // y

def di():
	return map(int, input().split())

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def si():
	return list(map(str, input()))

def indic():
	dic = {}
	for (index, value) in enumerate(input().split()):
		dic[int(index) + 1] = int(value)
	return dic
(n, p) = di()
a = li()
fir = a[0]
sec = sum(a) - fir
ans = fir % p + sec % p
for i in range(1, n):
	fir += a[i]
	sec -= a[i]
	temp = fir % p + sec % p
	if temp > ans:
		ans = temp
print(ans)


(n, p) = map(int, input().split())
seq = list(map(int, input().split()))
p1 = 0
p2 = 0
seqSum = sum(seq)
Sums = []
for i in range(n):
	p1 += seq[i]
	p2 = seqSum - p1
	Sums.append(p1 % p + p2 % p)
print(max(Sums))


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
s1 = arr[0]
s2 = sum(arr) - arr[0]
ans = [s1 % m + s2 % m]
for i in range(1, n - 1):
	s1 += arr[i]
	s2 -= arr[i]
	ans.append(s1 % m + s2 % m)
print(max(ans))


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
m = -1
s = sum(a)
sums = 0
for i in a:
	sums += i
	m = max(m, sums % p + (s - sums) % p)
print(m)


(n, p) = map(int, input().split())
A = list(map(int, input().split()))
highScore = 0
lSum = A[0]
rSum = sum(A[1:])
for i in range(len(A) - 1):
	score = lSum % p + rSum % p
	if score > highScore:
		highScore = score
	lSum += A[i + 1]
	rSum -= A[i + 1]
print(highScore)


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
pref = [a[0]]
for i in range(1, n):
	pref.append(pref[-1] + a[i])
tot = pref[-1]
ans = 0
for i in range(n - 1):
	ans = max(ans, pref[i] % p + (pref[-1] - pref[i]) % p)
print(ans)


(n, p) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
t1 = 0
t2 = sum(a)
res = sum(a) % p
for i in range(n):
	t1 += a[i]
	t2 -= a[i]
	t3 = t1 % p + t2 % p
	if res < t3:
		res = t3
print(res)


(n, p) = list(map(int, input().split()))
pre = [0] * 100100
A = list(map(int, input().split()))
for i in range(n):
	pre[i + 1] = (pre[i] + A[i]) % p
print(max(((pre[i] - pre[0]) % p + (pre[n] - pre[i]) % p for i in range(1, n))))


(n, p) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
sum1 = int(0)
sum2 = int(0)
for i in range(0, n):
	sum2 = sum2 + a[i]
k = n - 1
b = [0]
for i in range(0, k):
	sum1 = sum1 + a[i]
	sum2 = sum2 - a[i]
	b.append(sum1 % p + sum2 % p)
print(max(b))


line = input().split()
n = int(line[0])
p = int(line[1])
a = input().split()
suma = 0
for i in range(n):
	a[i] = int(a[i])
	suma += a[i]
Max = 0
sum = 0
for i in range(n - 1):
	sum += a[i]
	total = sum % p + (suma - sum) % p
	if total > Max:
		Max = total
print(Max)


(n, p) = map(int, input().split())
listA = list(map(int, input().split()))
sumA = sum(listA)
ans = []
v = 0
for i in range(n - 1):
	v += listA[i]
	sumA -= listA[i]
	ans.append(v % p + sumA % p)
print(max(ans))


(n, p) = (int(i) for i in input().split())
l = [int(i) for i in input().split()]
pref = [l[0] % p]
suff = [l[n - 1] % p]
for i in range(1, n - 1):
	pref.append((pref[i - 1] + l[i] % p) % p)
for i in range(1, n - 1):
	suff.append((suff[i - 1] + l[n - i - 1] % p) % p)
m = 0
suff = suff[::-1]
for i in range(n - 1):
	m = max(pref[i] + suff[i], m)
print(m)


(N, p) = list(map(int, input().split()))
A = list(map(int, input().split()))
sa = sum(A)
cursum = 0
ans = 0
for (i, a) in enumerate(A[:-1]):
	cursum += a
	score = cursum % p + (sa - cursum) % p
	ans = max(ans, score)
print(ans)


(n, p) = map(int, input().split())
arr = [int(b) for b in input().split()]
res = []
prefsums = [arr[0]]
for i in range(1, n):
	prefsums.append(prefsums[i - 1] + arr[i])
allsum = sum(arr)
if len(arr) == 2:
	print(arr[0] % p + arr[1] % p)
	exit()
for i in range(1, n - 1):
	res.append(prefsums[i] % p + (allsum - prefsums[i]) % p)
print(max(res))


(n, p) = map(int, input().split())
l = list(map(int, input().split()))
x = l[0]
z = sum(l) - x
s = x % p + z % p
for i in range(1, n - 1):
	x = x + l[i]
	z = z - l[i]
	t = x % p + z % p
	if t > s:
		s = t
print(s)


(n, m) = [int(x) for x in input().split(' ')]
numbers = [int(x) for x in input().split(' ')]
max_res = 0
total_sum = sum(numbers)
sum_thus_far = 0
for i in range(n - 1):
	tmp_a = sum_thus_far + numbers[i]
	tmp_b = total_sum - tmp_a
	tmp_sum = tmp_a % m + tmp_b % m
	if tmp_sum > max_res:
		max_res = tmp_sum
print(max_res)


(N, p) = list(map(int, input().split()))
A = list(map(int, input().split()))
sum1 = A[0]
sum2 = sum(A[1:])
ans = sum1 % p + sum2 % p
for i in range(1, N - 1):
	sum1 += A[i]
	sum2 -= A[i]
	ans1 = sum1 % p
	ans2 = sum2 % p
	ans = max(ans1 + ans2, ans)
print(ans)


(n, p) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [c % p for c in a]
s = sum(a)
sp = s % p
if sp == s or sp + 1 == p:
	print(sp)
else:
	print(sp + p)


(N, p) = map(int, input().split(' '))
A = [int(el) % p for el in input().split(' ')]
(S1, S2) = (A[0], sum(A[1:]) % p)
mx = S1 + S2
for i in range(1, N):
	S1 = (S1 + A[i]) % p
	S2 = (S2 - A[i]) % p
	if S1 + S2 > mx:
		mx = S1 + S2
print(mx)


(n, p) = map(int, input().split())
ar = [int(x) for x in input().split()]
res = 0
for i in ar:
	res += i
first = 0
mx = 0
for i in ar:
	first += i
	res -= i
	mx = max(mx, first % p + res % p)
print(mx)


np = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
max = 0
mod = []
sum = 0
for i in range(0, np[0]):
	sum += a[i]
	mod.append(sum % np[1])
index = 0
mm = 0
for i in range(0, np[0]):
	if mod[i] > mm:
		mm = mod[i]
		index = i
sum2 = 0
for i in range(index + 1, np[0]):
	sum2 += a[i]
sum2 = sum2 % np[1]
print(mod[index] + sum2)


s = input().split()
lis = input().split()
summ = 0
ans = []
sum1 = 0
sum2 = summ
for i in lis:
	summ += int(i)
sum2 = summ
for i in range(int(s[0]) - 1):
	sum1 += int(lis[i])
	sum2 -= int(lis[i])
	ans.append(sum1 % int(s[1]) + sum2 % int(s[1]))
ans.sort()
print(ans[len(ans) - 1])


(n, p) = map(int, input().split())
list1 = list(map(int, input().split()))
mx = 0
curr = 0
nxt = sum(list1)
for i in range(n - 1):
	curr += list1[i]
	nxt -= list1[i]
	mx = max(mx, curr % p + nxt % p)
print(mx)


line1 = list(map(int, input().split()))
nums = list(map(int, input().split()))
(n, p) = (line1[0], line1[1])
sum_all = sum(nums)
sum_left = nums[0]
sum_right = sum_all - sum_left
res = sum_left % p + sum_right % p
for i in range(1, n - 1):
	sum_left += nums[i]
	sum_right -= nums[i]
	temp = sum_left % p + sum_right % p
	res = max(res, temp)
print(res)


(n, p) = map(int, input().split())
a = [int(x) for x in input().split()]
s = sum(a)
ans = -1
psum = 0
for i in a:
	psum += i
	ans = max(ans, psum % p + (s - psum) % p)
print(ans)


(n, p) = [int(i) for i in input().split()]
soma = [0 for i in range(n + 1)]
for (idx, i) in enumerate(input().split()):
	soma[idx + 1] = soma[idx] + int(i) % p
r = -float('inf')
for i in range(1, n):
	r = max(r, soma[i] % p + (soma[n] - soma[i]) % p)
print(r)


np = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
l1 = [a[0]]
l2 = [a[np[0] - 1]]
for i in range(1, np[0] - 1):
	l1.append(l1[i - 1] + a[i])
	l2.append(l2[i - 1] + a[-(i + 1)])
max = 0
for i in range(0, np[0] - 1):
	if l1[i] % np[1] + l2[-(i + 1)] % np[1] > max:
		max = l1[i] % np[1] + l2[-(i + 1)] % np[1]
print(max)


(N, p) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
sum1 = 0
sum2 = sum(a)
ans = 0
for i in range(N - 1):
	sum1 += a[i]
	sum2 -= a[i]
	ans = max(ans, sum1 % p + sum2 % p)
print(ans)


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
forward = [a[0]]
for i in range(1, n):
	forward.append(forward[-1] + a[i])
sm = sum(a)
mx = -float('inf')
for i in range(n - 1):
	mx = max(mx, forward[i] % p + (sm - forward[i]) % p)
print(mx)


(n, mod) = map(int, input().split())
li = [int(i) for i in input().split()]
for i in range(1, n):
	li[i] += li[i - 1]
ma = 0
for i in range(n - 1):
	ma = max(ma, li[i] % mod + (li[n - 1] - li[i]) % mod)
print(ma)


(n, p) = map(int, input().split())
data = list(map(int, input().split()))
total = sum(data)
cur = data[0]
m = cur % p + (total - cur) % p
for i in range(1, n - 1):
	cur += data[i]
	m = max(m, cur % p + (total - cur) % p)
print(m)


(n, x) = map(int, input().split())
a = [int(i) for i in input().split()]
prefix_sums = []
for (ind, a_i) in enumerate(a):
	if ind != 0:
		prefix_sums.append(prefix_sums[ind - 1] + a_i)
	else:
		prefix_sums.append(a_i)
max_sum = 0
for prefix_sum in prefix_sums:
	max_sum = max(max_sum, prefix_sum % x + (prefix_sums[-1] - prefix_sum) % x)
print(max_sum)


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
c = [a[0]]
for i in range(1, len(a)):
	c.append(c[-1] + a[i])
sums = []
for i in range(len(c) - 1):
	sums.append(c[i] % p + (c[-1] - c[i]) % p)
print(max(sums))


(n, p) = [int(a) for a in input().strip().split(' ')]
e = [int(a) for a in input().strip().split(' ')]
max_sum = 0
s = sum(e)
current_s = 0
for i in e:
	current_s += i % p
	current_s %= p
	max_sum = max(max_sum, current_s + (s - current_s) % p)
print(max_sum)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
	a[i + 1] = (a[i + 1] + a[i]) % m
ans = 0
for i in range(1, n):
	x = a[i] + ((a[n] - a[i]) % m + m) % m
	ans = max(ans, x)
print(ans)