You are given a function $f(X)=X^2$. You are also given $\mbox{K}$ lists. The $i^{\mbox{th}}$ list consists of $N_i$ elements.

You have to pick one element from each list so that the value from the equation below is maximized: 

$S=(f(X_1)~+f(X_2)+~....~+f(X_k))$%$\mbox{M}$

$X_i$ denotes the element picked from the $i^{\mbox{th}}$ list . Find the maximized value $S_{max}$  obtained. 

$\gamma_{0}$ denotes the modulo operator. 

Note that you need to take exactly one element from each list, not necessarily the largest element. You add the squares of the chosen elements and perform the modulo operation. The maximum value that you can obtain, will be the answer to the problem. 

Input Format

The first line contains $2$ space separated integers $\mbox{K}$ and $\mbox{M}$. 

The next $\mbox{K}$ lines each contains an integer $N_i$, denoting the number of elements in the $i^{\mbox{th}}$ list, followed by $N_i$ space separated integers denoting the elements in the list. 

Constraints

$1\leq K\leq7$ 

$1\leq M\leq1000$ 

$1\leq N_i\leq7$ 

$1\le\textit{Magnitude of elements in list}\le10^9$  

Output Format

Output a single integer denoting the value $S_{max}$. 

Sample Input
3 1000
2 5 4
3 7 8 9 
5 5 7 8 9 10 

Sample Output
206

Explanation

Picking $5$ from the $\mbox{I}$^{st} list, $\mbox{9}$ from the $2$^{nd} list and $10$ from the $3$^{rd} list gives the maximum $\mbox{S}$ value equal to $(5^2+9^2+10^2)$%$\textbf{1000}$ = $\textbf{206}$.

Source: hackerrank | Difficulty: MEDIUM_HARD


Solutions:
from itertools import product
(K, M) = map(int, input().split())
L = []
for _ in range(K):
	L.append(list(map(int, input().split()))[1:])
print(max((sum((x ** 2 for x in val)) % M for val in product(*L))))


from collections import *
from itertools import *
a = [int(x) for x in input().split()]
k = a[0]
M = a[1]
l = []
for i in range(k):
	l.append([int(x) for x in input().split()][1:])
maxi = 0
for i in product(*l):
	maxi = max(maxi, sum(map(lambda x: x ** 2, i)) % M)
print(maxi)


def read_integers():
	return map(int, input().strip().split())
(k, m) = read_integers()
matrix = []
for _ in range(k):
	matrix.append(list(read_integers())[1:])

def max_pick(ind, val):
	if ind >= len(matrix):
		return val
	tmp_max = -1
	for i in matrix[ind]:
		tmp_max = max(tmp_max, max_pick(ind + 1, (val + i ** 2) % m))
	return tmp_max
print(max_pick(0, 0))


from itertools import product
(testcases, mmod) = [int(x) for x in input().strip().split()]
allary = []
for case in range(testcases):
	allary.append([int(x) for x in input().strip().split()[1:]])
mmax = 0
for p in product(*allary):
	mmax = max(sum((x ** 2 for x in p)) % mmod, mmax)
print(mmax)


import itertools
(tests, mod) = map(int, input().split())
maximum = 0
allLists = []
for t in range(tests):
	data = list(map(int, input().split()))
	data.pop(0)
	data = list(map(lambda x: x * x, data))
	allLists.append(data)
for each in itertools.product(*allLists):
	num = sum(each) % mod
	if num > maximum:
		maximum = num
print(maximum)


import itertools
(k, m) = map(int, input().split())
k_lists = []
for i in range(k):
	k_lists.append(list(map(int, input().split())))
	k_lists[-1].remove(k_lists[-1][0])
cross_p = list(itertools.product(*k_lists))

def getSum(p):
	t = 0
	for val in p:
		t += val ** 2
	return t % m
maximised = getSum(cross_p[0])
for item in cross_p:
	gotSum = getSum(item)
	if gotSum > maximised:
		maximised = gotSum
print(maximised)


from itertools import product
data = []
(k, M) = map(int, input().split())
for i in range(k):
	data.append(list(map(lambda x: (int(x) % M) ** 2 % M, input().split()[1:])))
max_val = 0
for el in product(*data):
	max_val = max(sum(el) % M, max_val)
print(max_val)


(k, m) = [int(x) for x in input().split()]
f = [[False] * m for _ in range(2)]
f[0][0] = True
(pre, now) = (1, 0)
for _ in range(k):
	(now, pre) = (pre, now)
	e = [int(x) for x in input().split()]
	for i in range(1, len(e)):
		for j in range(0, m):
			if f[pre][j]:
				f[now][(j + e[i] * e[i]) % m] = True
	for j in range(0, m):
		f[pre][j] = False
for i in range(m - 1, -1, -1):
	if f[now][i]:
		print(i)
		break


import math
import itertools
(K, M) = input().split()
mod = int(M)
elems_arr = [[int(x) ** 2 for x in input().split()[1:]] for _ in range(int(K))]
acc = 0
m = max([x % mod for x in [sum(tup) for tup in list(itertools.product(*elems_arr))]])
print(str(m))


from itertools import product
square = lambda x: int(x) ** 2
kAndM = list(map(int, input().split()))
k = kAndM[0]
m = kAndM[1]
combinationStore = []
for i in range(k):
	rawRowArray = list(map(square, input().split()))
	combinationStore.append(rawRowArray[1:])
combinationStore = list(product(*combinationStore))
functionResults = []
for combo in combinationStore:
	functionResults.append(sum(combo) % m)
print(max(functionResults))


from itertools import *
(k, m) = map(int, input().split())
l = [list(map(int, input().split()))[1:] for _ in range(k)]
mx = 0
for p in product(*l):
	mx = max(mx, sum((x ** 2 for x in p)) % m)
print(mx)


import itertools
f = lambda x: x * x
(K, M) = [int(x) for x in input().split()]
list = []
for _ in range(K):
	l = [int(x) for x in input().split()[1:]]
	list.append(l)
max = 0
for x in itertools.product(*list):
	sum = 0
	for y in x:
		sum += f(y)
	sum = sum % M
	max = max if max >= sum else sum
print(max)


(k, m) = map(int, input().split())
import itertools
ls = []
for _ in range(k):
	ls.append(map(lambda x: x ** 2, map(int, input().split()[1:])))
print(max(map(lambda x: x % m, map(sum, itertools.product(*ls)))))


from itertools import product
(t, m) = map(int, input().split())
ls = []
for i in range(t):
	tmp = map(int, input()[1:].split())
	tmp2 = [x ** 2 for x in tmp]
	ls.append(tmp2)
max = 0
for i in product(*ls):
	pro = 0
	for j in i:
		pro += j
	if pro % m > max:
		max = pro % m
print(max)


from itertools import product
(K, M) = list(map(int, input().split()))
N = (list(map(int, input().split()))[1:] for _ in range(K))
results = [sum((i ** 2 for i in x)) % M for x in product(*N)]
print(max(results))


from itertools import product

def readints():
	return [int(fld) for fld in input().split()]

def getcase():
	(nlists, m) = readints()
	lists = [readints()[1:] for _ in range(nlists)]
	return (m, lists)

def maxit(mod, lists):
	return max((sum((n * n for n in selection)) % mod for selection in product(*lists)))
print(maxit(*getcase()))


from itertools import product
(n, M) = map(int, input().split())
arr = []
for i in range(0, n):
	temp = list(map(int, input().split()))
	x = temp[0]
	for i in range(0, x + 1):
		temp[i] = temp[i] ** 2
	del temp[0]
	arr.append(temp)
P = product(*arr)
max = 0
for i in P:
	val = sum(i) % M
	if val > max:
		max = val
		temp = i
print(max)


from itertools import product
(k, m) = map(int, input().split())
l = []
for _ in range(k):
	l.append(list(map(lambda x: x ** 2, list(map(int, input().split()[1:])))))
print(max((sum(x) % m for x in product(*l))))


import itertools
(K, M) = [int(i) for i in input().strip().split()]
L = []
for _ in range(K):
	L.append([int(i) ** 2 for i in input().strip().split()[1:]])
print(max([sum(i) % M for i in itertools.product(*L)]))


from itertools import product
ints = lambda : list(map(int, input().split()))
squares = lambda xs: list(map(lambda x: x * x, xs))
(k, m) = ints()
x = list((squares(ints()[1:]) for i in range(k)))
print(max((sum(c) % m for c in product(*x))))


import itertools
(k, m) = map(int, input().split())
lists = []
for _ in range(k):
	(n, *L) = map(int, input().split())
	lists.append(L)
all_combinations = itertools.product(*lists)
max_result = 0
for combination in all_combinations:
	result = sum(map(lambda x: x ** 2, combination)) % m
	if result > max_result:
		max_result = result
print(max_result)


def increaseInds(inds, arr):
	i = 0
	while True:
		inds[i] += 1
		if inds[i] < len(arr[i]):
			return True
		else:
			inds[i] = 0
			i += 1
			if i == len(inds):
				return False
(K, M) = map(int, input().split())
Ns = []
for i in range(K):
	arr = list(map(int, input().split()))
	Ns.append(arr[1:])
max = 0
inds = [0 for x in range(K)]
while True:
	temp = 0
	for i in range(K):
		temp += Ns[i][inds[i]] * Ns[i][inds[i]]
	temp %= M
	if temp > max:
		max = temp
	if not increaseInds(inds, Ns):
		break
print(max)


(K, M) = map(int, input().split())
FinalList = list()
for i in range(K):
	line = list(map(int, input().split()))
	line = line[1:]
	FinalList.append(line)
from itertools import product
tempList = list(product(*FinalList))
SumList = list()
for myList in tempList:
	tempsum = 0
	for a in myList:
		tempsum += a ** 2
	SumList.append(tempsum % M)
print(max(SumList))


import itertools
(k, m) = map(int, input().split())
s = -1
for a in itertools.product(*[map(int, input().split()[1:]) for i in range(k)]):
	s = max(s, sum([i ** 2 for i in a]) % m)
print(s)


(K, M) = [int(i) for i in input().split()]
L = []

def dive(L, v):
	if not L:
		result.add(v)
		return
	for l in L[0]:
		dive(L[1:], (v + l) % M)
result = set()
for _ in range(K):
	L.append(list(set((int(i) ** 2 % M for i in input().split()[1:]))))
dive(L, 0)
print(max(result))


from itertools import product
(K, N) = map(int, input().split())
L = []
M = []
(SUM, SUM1) = (0, 0)
for i in range(K):
	L = list(map(int, input().split()))
	L = L[1:]
	L = set(L)
	M.append(L)
L = list(product(*M))
M = []
for i in L:
	for j in i:
		SUM = SUM + j * j
	SUM1 = SUM1 + SUM
	M.append(SUM1 % N)
	SUM1 = 0
	SUM = 0
print(max(M))


from itertools import product
(N, M) = map(int, input().split())
lists = []
for i in range(N):
	a = list(map(lambda x: int(x) ** 2, input().rstrip().split()[1:]))
	lists.append(a)
print(sum(max(list(product(*lists)), key=lambda x: sum(x) % M)) % M)


import itertools
line = input().split()
K = int(line[0])
M = int(line[1])
inputlists = []
for k in range(K):
	nextlist = list(map(int, input().split()))
	inputlists.append(nextlist[1:])
biglist = list(itertools.product(*inputlists))
maximum = 0
for tu in biglist:
	res = 0
	for x in tu:
		res += x ** 2
	res = res % M
	if res > maximum:
		maximum = res
print(maximum)


import itertools
(k, m) = map(int, input().split())
x = []
lengths = []
for i in range(k):
	line0 = list(map(int, input().split()))
	line1 = list(map(lambda x: x * x % m, line0[1:]))
	x.append(line1)
	lengths.append(line0[0])
maxs = 0
for t in itertools.product(*list(map(list, map(range, lengths)))):
	s = 0
	for i in range(k):
		s += x[i][t[i]]
		s %= m
	maxs = max(s, maxs)
print(maxs)


from itertools import product
(K, M) = map(int, input().split())
a = [[int(e) ** 2 for e in input().split()][1:] for _ in range(K)]
print(max((sum(e) % M for e in product(*a))))


data = input().split()
k = int(data[0])
m = int(data[1])
states = [0]
for i in range(0, k):
	newstates = []
	data = input().split()
	for st in data[1:]:
		d = int(st)
		for s in states:
			newtot = (d * d + s) % m
			if not newtot in newstates:
				newstates.append(newtot)
	states = newstates
print(max(states))


from itertools import product
(k, n) = [int(x) for x in input().split()]
L = []
for _ in range(k):
	L.append([int(x) for x in input().split()[1:]])
best = 0
for c in product(*L):
	s = sum([x * x for x in c]) % n
	best = max(best, s)
print(best)


import itertools
from collections import deque

def fun(listOfNums, d):
	total = 0
	for i in listOfNums:
		total += i % d * (i % d) % d
	return total
firtLineInfo = str(input()).split()
k = int(firtLineInfo[0])
m = int(firtLineInfo[1])
maxi = 0
listOfLists = deque([])
for i in range(k):
	listOfLists.append(deque([int(x) for x in str(input()).split()]))
	listOfLists[-1].popleft()
newList = list(itertools.product(*listOfLists))
for i in newList:
	if maxi < fun(i, m) % m:
		maxi = fun(i, m) % m
print(maxi)


from itertools import product
(k, m) = map(int, input().split())
modulo = {}
for _ in range(k):
	(_, *numbers) = map(lambda x: int(x) ** 2 % m, input().split())
	if not modulo:
		for number in numbers:
			modulo[number] = 1
	else:
		(keys, modulo) = (list(modulo.keys()), {})
		for (a, b) in product(numbers, keys):
			modulo[(a + b) % m] = 1
print(sorted(modulo.keys())[-1])


import itertools
(k, m) = map(int, input().split())
res = 0
lst = []
for _ in range(k):
	vls = [int(x) ** 2 % m for x in input().split()[1:]]
	lst.append(sorted(vls))
b = itertools.product(*lst)
print(max([sum(i) % m for i in b]))


from itertools import product

def maximizeIt(arrays, K, M):
	print(max([sum([elem ** 2 for elem in prod]) % M for prod in list(product(*arrays))]))
(K, M) = map(int, input().split())
arrays = [list(map(int, input().split()[1:])) for i in range(K)]
maximizeIt(arrays, K, M)


from itertools import product
(k, m) = map(int, input().split())
s = list((list(map(lambda n: int(n) ** 2, input().split()))[1:] for _ in range(k)))
max_s = 0
for e in product(*s):
	total = sum(e) % m
	if total > max_s:
		max_s = total
print(max_s)


from itertools import product
(K, M) = map(int, input().split())
lines = []
for i in range(K):
	l = list(map(int, input().split()))
	l.remove(l[0])
	lines.append(l)
s = []
for item in product(*lines):
	s.append(sum((x ** 2 for x in item)) % M)
print(max(s))


from itertools import product
(k, m) = map(int, input().split())
x = [[] for i in range(k)]
for i in range(k):
	x[i] = list(map(int, input().split()))
	x[i] = x[i][1:]
p = list(product(*x))
max = 0
for i in p:
	s = 0
	for j in i:
		s = s + pow(j, 2)
	if s % m > max:
		max = s % m
print(max)


from itertools import product
(K, M) = map(int, input().split())
li = []
for i in range(K):
	li.append(list(map(int, input().split()))[1:])
out = list(product(*li))
res = []
for i in out:
	s = 0
	for k in i:
		s = s + k ** 2
	res.append(s % M)
print(max(res))


from itertools import product
n = list(map(int, input().split()))
l = []
for i in range(n[0]):
	s = list(map(int, input().split()))
	del s[0]
	l.append(s)
k = product(*l)
x = 0

def sq(a):
	return int(a ** 2)
z = []
for i in k:
	a = sum(list(map(sq, i)))
	z.append(a % n[1])
print(max(z))


def recursive_add(count, options, level, M, best):
	if level == 0:
		for o in options[level]:
			temp = (count + o) % M
			if temp > best:
				best = temp
		return best
	else:
		for o in options[level]:
			best = recursive_add(count + o, options, level - 1, M, best)
		return best
(T, M) = list(map(int, input().split()))
options = []
for _ in range(T):
	case = list(map(int, input().split()))
	case = set(case[1:])
	options.append([n * n for n in case])
print(recursive_add(0, options, len(options) - 1, M, 0))


(K, M) = [int(value) for value in input().split()]
ls = []
for index in range(K):
	ls.append([int(value) % M * int(value) % M for value in input().split()[1:]])
sums = set(ls[0])
for index in range(1, K):
	next_up = ls[index]
	new_sums = set()
	for value1 in sums:
		for value2 in next_up:
			new_sums.update([value1 + value2])
	sums = new_sums
print(max(list(map(lambda x: x % M, sums))))


from itertools import *
(n, m) = input().split()
n = int(n)
m = int(m)
l = []
for i in range(n):
	l.append(input().split())
	l[i].pop(0)
for i in range(n):
	for j in range(len(l[i])):
		l[i][j] = int(l[i][j])
l = list(product(*l))
maxm = 0
sum1 = 0
for i in range(len(l)):
	for j in l[i]:
		sum1 = (sum1 + j * j % m) % m
	if sum1 % m > maxm:
		maxm = sum1 % m
	sum1 = 0
print(maxm)


from itertools import product
(k, m) = map(int, input().split())
lists = ([int(n) ** 2 for n in input().split()[1:]] for _ in range(k))
print(max((sum(p) % m for p in product(*lists))))


from itertools import product
line = list(map(int, input().split()))
k = line[0]
m = line[1]
arr = []
for i in range(0, k):
	lst = list(map(int, input().split()))
	n = lst[0]
	a = []
	for j in range(1, n + 1):
		a.append(lst[j] ** 2)
	a.sort()
	arr.append(a)
tuplesArr = product(*arr)
maximum = 0
for t in tuplesArr:
	summ = 0
	for k in t:
		summ += k
	res = summ % m
	if res > maximum:
		maximum = res
print(maximum)


from itertools import product
(k, m) = input().split()
ls = []
for _ in range(int(k)):
	ls.append([x * x for x in map(int, input().split()[1:])])
func = lambda x: sum(x) % int(m)
print(str(func(max(list(product(*ls)), key=func))))


from itertools import product
(k, m) = map(int, input().split())
l = []
for i in range(k):
	l.append(list(map(int, input().split()))[1:])
ans = max((sum(map(lambda x: x ** 2, y)) % m for y in product(*l)))
print(ans)


import itertools
(k, m) = [int(x) for x in input().split()]
lsts = []
for _ in range(k):
	lsts.append(sorted([int(x) ** 2 % m for x in input().split()][1:]))
possibilities = itertools.product(*lsts)
maximum = max([sum(t) % m for t in possibilities])
print(maximum)


from itertools import product
S = list()
Result = list()
t = list(map(int, input().split()))
for i in range(t[0]):
	S.append(list((x * x for x in list(map(int, input().split()))[1:])))
for i in list(product(*S)):
	Result.append(sum(i) % t[1])
print(max(Result))


import sys
(k, m) = map(int, sys.stdin.readline().split())
nums = []
for i in range(k):
	tmp = list(map(lambda x: (int(x) % m) ** 2 % m, sys.stdin.readline().split()))
	nums.append(tmp[1:])
indices = [0] * k
maxsum = 0
noend = True
while noend:
	tsum = 0
	for i in range(k):
		tsum += nums[i][indices[i]]
		tsum %= m
	if tsum > maxsum:
		maxsum = tsum
	indices[0] += 1
	for i in range(k):
		if indices[i] == len(nums[i]):
			indices[i] = 0
			if i + 1 >= k:
				noend = False
				break
			indices[i + 1] += 1
print(maxsum)


import itertools
(k, m) = list(map(int, input().split()))
main_ar = []
for i in range(k):
	ar = list(map(int, input().split()))
	main_ar.append(ar[1:])
all_combination = itertools.product(*main_ar)
result = 0
for single_combination in all_combination:
	result = max(sum([x * x for x in single_combination]) % m, result)
print(result)


import itertools

def f(a):
	return a ** 2
(k, m) = map(int, input().split())
l = list((list(map(f, map(int, input().split()[1:]))) for i in range(k)))
max = 0

def p(l):
	return sum(l) % m
for x in itertools.product(*l):
	t = p(x)
	if t > max:
		max = t
print(max)


from itertools import *
from functools import reduce
a = list(map(int, input().split()))
k = a[0]
m = a[1]
x = []
for i in range(k):
	x.append(input())
y = []
for i in x:
	y.append(i.split()[1:])
z = list(product(*y))
final = []

def square(x):
	return x * x

def sum(x, y):
	return x + y
for i in z:
	final.append(reduce(sum, list(map(square, map(int, i)))) % m)
print(sorted(final, reverse=True)[0])


(k, m) = map(int, input().split())
li = [tuple(map(lambda x: int(x) ** 2 % m, input()[2:].split())) for _ in range(k)]
s1 = set([0])
for i in li:
	s2 = set()
	for j in i:
		for k in s1:
			s2.add((k + j) % m)
	s1 = s2
print(max(s1))


import itertools
(k, m) = map(int, input().split())
ls = []
for _ in range(k):
	ls.append(map(lambda x: x ** 2, map(int, input().split()[1:])))
print(max(map(lambda x: x % m, map(sum, itertools.product(*ls)))))


from itertools import product
(K, M) = [int(x) for x in input().split()]
LL = []
for _ in range(K):
	(N, *L) = [int(x) for x in input().split()]
	L = [x * x for x in L]
	LL.append(L)
m = 0
for p in product(*LL):
	s = sum(p)
	if s % M > m:
		m = s % M
print(m)


from itertools import product
(K, M) = map(int, input().split())
l = []
for _ in range(K):
	n = list(map(int, input().split()))
	l.append(n[1:])
S = []
for i in list(product(*l)):
	S.append(sum([x ** 2 for x in i]) % M)
print(max(S))


import itertools
(k, m) = map(int, input().split())
N = []
for _ in range(k):
	N.append(list(map(int, input().split()))[1:])
print(max(map(lambda xs: sum(map(lambda n: n ** 2, xs)) % m, itertools.product(*N))))


import itertools
(k, m) = map(int, input().split())
l = []
for i in range(k):
	l.append(list(map(int, input().split()[1:])))
t = itertools.product(*l)
max_mod = 0
for el in t:
	s = sum(map(lambda x: x * x, el)) % m
	if s > max_mod:
		max_mod = s
print(max_mod)


from itertools import product
(m, n) = input().split()
a = []
for i in range(int(m)):
	z = []
	z = list(map(int, input().split()))
	temp = z[0]
	z.remove(temp)
	a.append(z)
	q = []
for i in list(product(*a)):
	k = list(map(lambda x: x ** 2, i))
	q1 = sum(k)
	q.append(q1 % int(n))
print(max(q))


def readints():
	return [int(fld) for fld in input().split()]

def newposs(poss, arr, MOD):
	arrsq = [elt * elt % MOD for elt in arr]
	return set(((a + b) % MOD for a in arrsq for b in poss))
(k, m) = readints()
poss = {0}
for _ in range(k):
	(n, *arr) = readints()
	assert len(arr) == n
	poss = newposs(poss, arr, m)
print(max(poss))


from itertools import product
from functools import reduce
(k, m) = map(int, input().split())
arr = list()
for i in range(k):
	curr = input().split(' ', 1)[1]
	arr.append(list((int(i) ** 2 for i in curr.split())))
arr = list((reduce(lambda x, y: x + y, i) for i in list(product(*arr))))
res = 0
for i in arr:
	res = max(res, i % m)
print(res)


(n, M) = map(int, input().split())

def intPow(x):
	return int(x) ** 2
stuff = []
for i in range(n):
	lst = list(map(intPow, input().split()[1:]))
	stuff.append(lst)

def combinations(i, stuff, sum):
	if i == len(stuff):
		board.append(sum % M)
	else:
		for j in range(len(stuff[i])):
			combinations(i + 1, stuff, sum + stuff[i][j])
board = []
for i in range(len(stuff[0])):
	sum = 0
	sum += stuff[0][i]
	combinations(1, stuff, sum)
print(max(board) % M)


from itertools import product
(K, M) = map(int, input().split())
(r, s) = ([], set())
for _ in range(K):
	r.append(list(map(int, input().split()))[1:])
j = set(product(*r))
for i in j:
	total = 0
	for m in i:
		total += m ** 2
	s.add(total % M)
print(max(s))


from itertools import *
(k, m) = map(int, input().split())
n = []
for _ in range(k):
	n.append(map(int, input().split()[1:]))
maxx = -1
for i in product(*n):
	maxx = max(sum(map(lambda x: x ** 2, i)) % m, maxx)
print(maxx)


import itertools
(k, m) = map(int, input().split())
l = []
max_s = 0
max_t = None
for n in range(k):
	l.append(list(map(int, input().split()))[1:])
for t in itertools.product(*l):
	s = 0
	for i in t:
		s += i * i
	s %= m
	if s > max_s:
		max_s = s
print(max_s)


import itertools
(k, m) = list(map(int, input().split()))
lsts = list()
for i in range(k):
	lst = list(map(int, input().split()))[1:]
	lsts.append(list((x ** 2 for x in lst)))
ans = 0
for p in itertools.product(*lsts):
	s = sum(p) % m
	if s > ans:
		ans = s
print(ans)


import sys

def f(x):
	return x ** 2

def seqgen(n):
	if not n:
		return [[]]
	else:
		return [[i] + seq for seq in seqgen(n[1:]) for i in n[0]]

def maxs(M, seqs):
	return max([sum(map(f, seq)) % M for seq in seqs])
line = next(sys.stdin)
(K, M) = [int(x) for x in line.rstrip().split()]
N = [[int(x) for x in line.rstrip().split()[1:]] for line in sys.stdin]
print(maxs(M, seqgen(N)))


import itertools
(K, M) = map(int, input().split())
l = []
for _ in range(K):
	l.append(list(map(int, input().split()))[1:])
ans = 0
for tup in itertools.product(*l):
	tmp = 0
	for x in tup:
		tmp = (tmp + x * x) % M
	ans = max(ans, tmp)
print(ans)


from itertools import product
(nb, M) = map(int, input().split())
ls = [[0]] * nb
for i in range(nb):
	ls[i] = list(map(lambda x: (x % M) ** 2 % M, map(int, input().split())))[1:]
ma = max(map(lambda xs: sum(xs) % M, product(*ls)))
print(ma)


import itertools
(k, m) = str(input()).strip().split()
lines = []
for i in range(int(k)):
	line = list(map(int, str(input()).strip().split()))
	line.pop(0)
	lines.append(line)
(result, best) = (None, None)
products = sorted(set(itertools.product(*lines)))
for p in products:
	fx = map(lambda x: pow(x, 2), p)
	r = sum(fx) % int(m)
	if result is None or r > result:
		(result, best) = (r, p)
print(int(result))


import itertools
__author__ = 'namii'
(K, M) = map(int, input().split())
L = []
for i in range(K):
	current_line = list(map(lambda x: x % M, map(int, input().split()[1:])))
	L.append(current_line)
tulo = itertools.product(*L)
maksimi = 0
for item in tulo:
	summa = 0
	for number in item:
		summa = (number ** 2 % M + summa) % M
	maksimi = max(maksimi, summa)
print(maksimi)


from itertools import product
(k, m) = map(int, input().split())
data = list()
for i in range(k):
	data.append([x ** 2 for x in map(int, input().split())])
	data[i].pop(0)
tmp = list(product(*data))
out = [sum(x) % m for x in tmp]
print(max(out))


from itertools import product
import operator
(K, M) = map(int, input().split())
N = []
for x in range(K):
	n = list(map(lambda x: int(x) ** 2, input().split()))
	n.pop(0)
	N.append(n)
prods = product(*N)
sumprod = dict()
for x in prods:
	sumprod[x] = sum(x) % M
print(sumprod[max(sumprod, key=sumprod.get)])


from itertools import product
(K, M) = map(int, input().split())
N = []
for _ in range(K):
	N.append(list(map(int, input().split()))[1:])
MAX = -1
for i in product(*N):
	MAX = max(sum(map(lambda x: x ** 2, i)) % M, MAX)
print(MAX)


(K, M) = map(int, input().split())
N = []
for i in range(0, K):
	N.append(list(map(int, input().split())))
maxs = 0
fg = ff = fe = fd = fc = fb = False
for a in range(1, N[0][0] + 1):
	if K > 1:
		for b in range(1, N[1][0] + 1):
			if K > 2:
				for c in range(1, N[2][0] + 1):
					if K > 3:
						for d in range(1, N[3][0] + 1):
							if K > 4:
								for e in range(1, N[4][0] + 1):
									if K > 5:
										for f in range(1, N[5][0] + 1):
											if K > 6:
												for g in range(1, N[6][0] + 1):
													s = (N[0][a] ** 2 + N[1][b] ** 2 + N[2][c] ** 2 + N[3][d] ** 2 + N[4][e] ** 2 + N[5][f] ** 2 + N[6][g] ** 2) % M
													fg = True
													if s > maxs:
														maxs = s
											if fg:
												continue
											s = (N[0][a] ** 2 + N[1][b] ** 2 + N[2][c] ** 2 + N[3][d] ** 2 + N[4][e] ** 2 + N[5][f] ** 2) % M
											ff = True
											if s > maxs:
												maxs = s
									if fg or ff:
										continue
									s = (N[0][a] ** 2 + N[1][b] ** 2 + N[2][c] ** 2 + N[3][d] ** 2 + N[4][e] ** 2) % M
									fe = True
									if s > maxs:
										maxs = s
							if fg or ff or fe:
								continue
							s = (N[0][a] ** 2 + N[1][b] ** 2 + N[2][c] ** 2 + N[3][d] ** 2) % M
							fd = True
							if s > maxs:
								maxs = s
					if fg or ff or fe or fd:
						continue
					s = (N[0][a] ** 2 + N[1][b] ** 2 + N[2][c] ** 2) % M
					fc = True
					if s > maxs:
						maxs = s
			if fg or ff or fe or fd or fc:
				continue
			s = (N[0][a] ** 2 + N[1][b] ** 2) % M
			fb = True
			if s > maxs:
				maxs = s
	if fg or ff or fe or fd or fc or fb:
		continue
	s = N[0][a] ** 2 % M
	if s > maxs:
		maxs = s
print(maxs)


from itertools import *
(k, m) = tuple(map(int, input().split()))
list_sets = []
list_sets = [set(map(int, input()[1:].split())) for x in range(k)]
print(max([sum(map(lambda x: x * x, combo)) % m for combo in product(*list_sets)]))


import math
import sys
(k, m) = map(int, sys.stdin.readline().split())
mod = [False] * m
mod[0] = True
for nline in range(k):
	l = list(map(int, sys.stdin.readline().split()))[1:]
	nmod = [False] * m
	for x in l:
		for j in range(m):
			if mod[j]:
				nmod[(j + x * x) % m] = True
	mod = nmod
print(max([i for i in range(m) if mod[i]]))


import itertools
[K, M] = list(map(int, input().split()))
squares = []
for i in range(K):
	temp = input().split()
	temp = [int(x) ** 2 for x in temp[1:]]
	squares.append(temp)
maxSum = 0
for i in itertools.product(*squares):
	temp = sum(i) % M
	if maxSum < temp:
		maxSum = temp
print(maxSum)


import itertools
(k, m) = input().split()
print(max([sum(i) % int(m) for i in itertools.product(*[[pow(int(x), 2) for x in input().split()][1:] for _ in range(int(k))])]))


import sys

def indices(values):
	ind = [-1] * len(values)
	cur = 0
	while cur >= 0:
		if cur < len(ind):
			ind[cur] += 1
			if ind[cur] == len(values[cur]):
				ind[cur] = -1
				cur -= 1
			else:
				cur += 1
		else:
			yield ind
			cur -= 1

def maxsum(values, mod):
	maxres = 0
	for idx in indices(values):
		res = sum([pow(values[i][j], 2) for (i, j) in enumerate(idx)]) % mod
		if res > maxres:
			maxres = res
	return maxres

def run():
	inp = sys.stdin.readlines()
	(_, mod) = [int(v) for v in inp[0].split()]
	values = []
	for line in inp[1:]:
		values.append([int(v) for v in line.split()[1:]])
	print(maxsum(values, mod))
run()


import itertools
(K, M) = map(int, input().split())
data = (list(map(int, input().split()[1:])) for _ in range(K))
mx = 0
for t in itertools.product(*data):
	tmp = 0
	for n in t:
		tmp += n * n
	if tmp % M > mx:
		mx = tmp % M
print(mx)


def get_max_s(s, mod, s_max, cur, index):
	if index >= len(s):
		return cur % mod
	for val in s[index]:
		s_max = max(s_max, get_max_s(s, mod, s_max, cur + val ** 2, index + 1))
	return s_max
(K, M) = map(int, input().split())
lst = []
for k in range(K):
	(i, S) = input().split(maxsplit=1)
	lst.append(list(map(int, S.split())))
print(get_max_s(lst, M, 0, 0, 0))


from itertools import product
(k, m) = input().split()
m = int(m)
k = int(k)
lists = []
for line in range(k):
	next_list = input().split()
	next_list.pop(0)
	lists.append(set(map(int, next_list)))
one_from_each = product(*lists)
print(max([sum(map(lambda x: x * x, combo)) % m for combo in one_from_each]))


def solve(M, nums, index, tres):
	if index == len(nums):
		return sum([x * x for x in tres]) % M
	ret = 0
	for num in nums[index]:
		tres.append(num)
		ret = max(ret, solve(M, nums, index + 1, tres))
		tres.pop()
	return ret
(K, M) = [int(x) for x in input().split()]
nums = []
for _ in range(K):
	nums.append([int(x) for x in input().split()][1:])
print(solve(M, nums, 0, []))


from itertools import product
I = [int(x) for x in input().split()]
N = [[int(x) ** 2 for x in input().split()[1:]] for _ in range(I[0])]
print(max([sum(x) % I[1] for x in product(*N)]))


import re

def DFS(depth, now, mat, M):
	if depth == len(mat):
		return now % M
	max1 = 0
	for i in range(len(mat[depth])):
		max1 = max(max1, DFS(depth + 1, now + mat[depth][i], mat, M))
	return max1

def main():
	(K, M) = map(int, input().split())
	mat = []
	for _ in range(K):
		lst = [int(x * x) for x in map(int, input().split())]
		mat.append(lst[1:])
	print(DFS(0, 0, mat, M))
main()


import itertools
(K, M) = map(int, input().split())
lines = []
m = 0
for _ in range(K):
	lines.append(list(map(int, input().split()))[1:])
p = itertools.product(*lines)
summ = 0
for c in p:
	summ = 0
	for i in c:
		summ += i ** 2
	result = summ % M
	if result > m:
		m = result
print(m)