Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N=int(input())
S_dict={}

for s_idx in range(N):
    s = input()
    
    if s not in S_dict.keys():
        S_dict[s]=1
    else:
        S_dict[s]+=1

s_max=0
s_max_key=[]

for s_key in S_dict.keys():
    if s_max < S_dict[s_key]:
        s_max_key=[]
        s_max=S_dict[s_key]
        s_max_key.append(s_key)
    elif s_max == S_dict[s_key]:
        s_max=S_dict[s_key]
        s_max_key.append(s_key)
        
s_max_key.sort()

for ans in s_max_key:
    print(ans)

### FIXED CODE ###

N = int(input())
 
counter = {}
 
for i in range(N):
    temp = input()
    if temp not in counter:
        counter.update({temp : 1})
    else:
        counter.update({temp : counter[temp] + 1})
 
m = max(counter.values())
        
ans = []    
 
for a,b in counter.items():
    if b == m:
        ans.append(a)
    
ans.sort()
 
for i in ans:
    print(i)
### BUGGY CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import queue

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

    dp = [[[0 for _ in range(3)] for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, a in enumerate(A):
        for s in range(S + 1):
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += (dp[i][s][1] + dp[i][s][0]) % mod + (
                0 if s - a < 0 else dp[i][s - a][0] + dp[i][s - a][1]
            ) % mod
            dp[i + 1][s][2] += (
                sum(dp[i][s]) % mod
                + (0 if s - a < 0 else dp[i][s - a][1] + dp[i][s - a][0]) % mod
            )

            dp[i + 1][s][0] %= mod
            dp[i + 1][s][1] %= mod
            dp[i + 1][s][2] %= mod

    print(dp[N][S][2])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

    dp = [(0, 0, 0) for _ in range(S + 1)]
    dp[0] = (1, 1, 1)

    for a in A:
        for s in range(S, -1, -1):
            d1 = dp[s][0]
            d2 = (dp[s][1] + (0 if s - a < 0 else dp[s - a][1]) + d1) % mod
            d3 = (dp[s][2] + (0 if s - a < 0 else dp[s - a][1]) + d2) % mod
            dp[s] = (d1, d2, d3)

    print((dp[S][2] - dp[S][1]) % mod)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

#PypyでもTLE A[:half]のような箇所が遅い？
# -->二分探索のスタート地点を変えるだけで処理すると毎回新規リストを作らなくなる

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)


### FIXED CODE ###

#PypyでもTLE A[:half]のような箇所が遅い？

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
az = [0] * n
c = 0
for i in range(n)[::-1]:
    if a[i] == 0:
        c += 1
        az[i] = c
    else:
        c = 0
res = 0
for i in range(n):
    res += 1
    total = a[i]
    c = 1
    while c <= n - i - 1:
        if az[i+c] != 0:
            res += az[i+c]
            c += az[i+c]
            continue
        tmp = total ^ a[i+c]
        if total + a[i+c] == tmp:
            res += 1
            total = tmp
        else:
            break
        c += 1
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

ans, r = 0, 0
SUM, XOR = 0, 0

for l in range(N):
    while (r < N) and (SUM + A[r] == XOR ^ A[r]):
        SUM += A[r]
        XOR ^= A[r]
        r += 1

    ans += (r - l)
    SUM -= A[l]
    XOR ^= A[l]
print(ans)
### BUGGY CODE ###

n = int(input())

a = list(map(int, input().split()))


total = 0
for i in range(n-1):
    for j in a[i+1:]:
        total = (total+a[i]*j)%(10**9+7)
print(total)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 
 
print(ans % mod)
### BUGGY CODE ###

from heapq import *
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def size(self,x):
    return -size.parents[self.find(x)]
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
n=int(input())
X=[]
Y=[]
edge=[] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

### FIXED CODE ###

from heapq import *
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def size(self,x):
    return -size.parents[self.find(x)]
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
n=int(input())
X=[]
Y=[]
edge=[] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)
### BUGGY CODE ###

N=int(input())
List=list(map(int,input().split()))

count=0
for l in range(N):
    Left=Right=0
    for r in range(0,N-l):
        Left^=List[l+r]
        Right+=List[l+r]
        if Left==Right:
            count+=1
        elif Left<Right:
        	break

print(count)

### FIXED CODE ###

N=int(input())
List=list(map(int,input().split()))

count=0
SumL=SumR=0
R=0
for L in range(N):
    if L>R:
        R=L
    while R<N and SumL^List[R]==SumR+List[R]:
        SumR+=List[R]
        SumL^=List[R]
        R+=1

    SumR-=List[L]
    SumL^=List[L]
    count += R-L

print(count)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
cnt=0
for r in range(N//R+1):
    for g in range((N-r*R+1)//G+1):
        for b in range((N-r*R-g*G+1)//B+1):
            if R*r+G*g+B*b==N:
                cnt+=1                
print(cnt)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
cnt=0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        b=N-G*g-R*r
        if b%B==0 and b>=0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

from heapq import heappop, heappush
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 7
d = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dijkstra():
    que = []
    for i in range(4):
        d[x1][y1][i] = 0
        heappush(que, (0, x1, y1, i))
    
    while len(que):
        dist, cur_x, cur_y, dir = heappop(que)
    
        for i, (dx, dy) in enumerate(move):
            memo = dist
            if i != dir:
                memo = -(-dist // k) * k
            
            to_x, to_y = cur_x + dx, cur_y + dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y][i] > memo + 1:
                    d[to_x][to_y][i] = memo + 1
                    heappush(que, (memo + 1, to_x, to_y, i))

dijkstra()
if all(d[x2][y2][i] == inf for i in range(4)):
    print(-1)
else:
    print(-(-min(d[x2][y2]) // k))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

def get_min_compress_num(h, w, min_num):
    if h == 0:
        min_num_h = min_num
    else:
        add_min_num_h = 0 if HW_list[h][w] == HW_list[h - 1][w] else 1
        min_num_h = get_min_compress_num(h - 1, w, min_num + add_min_num_h)
    if w == 0:
        min_num_w = min_num
    else:
        add_min_num_w = 0 if HW_list[h][w] == HW_list[h][w - 1] else 1
        min_num_w = get_min_compress_num(h, w - 1, min_num + add_min_num_w)
    return(min(min_num_h, min_num_w))

add_adjust = 1 if HW_list[0][0] == "#" else 0
print(get_min_compress_num(H - 1, W - 1, 0) + add_adjust)

### FIXED CODE ###

# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

dp = [[H * W] * W] * H

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            min_num_h = H * W
        else:
            min_num_h = dp[i - 1][j] + (0 if HW_list[i][j] == HW_list[i - 1][j] else 1)
        if j == 0:
            min_num_w = H * W
        else:
            min_num_w = dp[i][j - 1] + (0 if HW_list[i][j] == HW_list[i][j - 1] else 1)
        dp[i][j] = min(min_num_h, min_num_w)

print(dp[H - 1][W - 1] // 2 + (1 if HW_list[0][0] == "#" or HW_list[H - 1][W - 1] == "#" else 0))
### BUGGY CODE ###

N = int(input())
array = list(map(int,input().split()))
pro = [ array[i]*sum(array[i+1:N]) for i in range(N-1) ]
print(sum(pro)%(10**9+7))

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
ans = 0
kuso = sum(array)
for i in range(N-1):
  kuso -= array[i]
  ans += array[i]*kuso  
print( ans%(10**9+7) )
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    c = 1
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
            c = c * (cnt + 1)

    if temp != 1:
        arr.append([temp, 1])
        c = c * (1 + 1)

    if arr == []:
        arr.append([n, 1])
        c = c * (1 + 1)

    return c


n = int(input())
ans = 0
for i in range(1, n):
    ans += factorization(n - i)
print(ans - 1)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
    ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    q_i = input().split(' ')
    t_i = q_i[0]
    if t_i == '1':
        s = s[::-1]
    else:
        f_i = q_i[1]
        if f_i == '1':
            s = q_i[2] + s
        else:
            s = s + q_i[2]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
is_r = False
f_list = []
b_list = []

for i in range(q):
    q_i = input().split(' ')
    t_i = q_i[0]
    if t_i == '1':
        is_r = not is_r
    else:
        f_i = q_i[1]
        if (f_i == '1' and not is_r) or (f_i == '2' and is_r):
            f_list.append(q_i[2])
        else:
            b_list.append(q_i[2])

f_list = f_list[::-1]
f_list.append(s)
f_list.extend(b_list)
s = ''.join(f_list) if not is_r else ''.join(f_list)[::-1]
print(s)
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import math
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()

n=2**(int(math.log2(n))+1)

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return set([])
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   
   print(len(qr(i-1,c,0,0,n)))
   
 q-=1


### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[0 for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return 0
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,1<<(ord(s[i])-ord("a")))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,1<<(ord(c)-ord("a")))
 else:
   c=int(c)
   x=0
   z=qr(i-1,c,0,0,n)
   while z:
     if z%2==1:
        x+=1
     z>>=1
   print(x)
 q-=1
### BUGGY CODE ###

#ABC 085C
import sys
f = 1
n,y = map(int,input().split())
for s in range(2001):
    for t in range(2001):
        for z in range(2001):
            if y-(10000*s+5000*t+1000*z) == 0 and s+t+z == n  :
                print(s,t,z)
                f = 0
                sys.exit()
if f == 1:
    print(-1,-1,-1)

### FIXED CODE ###

N,Y = map(int,input().split())
f = 0
loop = 0

for x in range(2001):
    for y in range(2001):
        z = N - x - y
        if 10000*x + 5000*y + 1000*z == Y and z >= 0:
            print(x,y,z)
            f = 1
            loop = 1
            break
    if loop == 1:
        break
if f == 0:
    print('-1','-1','-1')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if n % 2 == 0:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[len(a)-i-1]
        if a[i] == 0 or a[len(a)-i-1] == 0:
            ans = 0
            exit

if n % 2 == 1:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[len(a)-i-1]
        if a[i] == 0 or a[len(a)-i-1] == 0:
            ans = 0
            exit
        
    ans *= a[len(a)//2+1]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
if a[0] == 0:
    ans = 0
    print(ans)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

print(ans)
### BUGGY CODE ###

from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            cnt = 0
            q = deque([(i, j, cnt)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((20 * ii + jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (20 * (ii + 1) + jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (20 * ii + (jj + 1)) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (20 * (ii - 1) + jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (20 * ii + (jj - 1)) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            v = set()
            q = deque([(i, j, 0)])
            v.add((i, j))
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                    v.add((ii + 1, jj))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                    v.add((ii, jj + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                    v.add((ii - 1, jj))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
                    v.add((ii, jj - 1))
    return ret


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
import copy

n = int(input())	
orders = [deque(list(map(int, input().split()))) for _ in range(n)]

cnt = 0
finished = set()
while True:
	impossible = True
	skip = copy.deepcopy(finished)
	#print(orders)
	for i in range(n):	
		if i not in skip and orders[i][0] - 1 not in skip and orders[orders[i][0] - 1][0] - 1 == i:				
			a = i
			b = orders[i][0] - 1
			impossible = False
			skip.add(a)
			skip.add(b)
			orders[orders[i][0] - 1].popleft()
			orders[i].popleft()

			if len(orders[i]) == 0:
				finished.add(a)
			if len(orders[b]) == 0:
				finished.add(b)
	cnt += 1

	if len(finished) == n:
		print(cnt)
		break

	if impossible:
		print(-1)
		break

### FIXED CODE ###

from collections import deque

n = int(input())
orders = [deque([x - 1 for x in list(map(int, input().split()))] + [-1]) for _ in range(n)]

nxt = [orders[i].popleft() for i in range(n)]
days = [0 for _ in range(n)]

q = deque([i for i in range(n)])
while q:
	a = q.popleft()
	b = nxt[a]
	if nxt[nxt[a]] == a:
		days[a], days[b] = [max(days[a], days[b]) + 1 for _ in range(2)]
		nxt[a] = orders[a].popleft()
		nxt[b] = orders[b].popleft()
		q.append(a)
		q.append(b)

if sum(nxt) == -n:
	print(max(days))
else:
	print(-1)
### BUGGY CODE ###

import copy

t_list = []
n, m, q = map(int, input().split())
my_set = set()
for i in range(q):
    t_list.append(list(map(int, input().split())))
    my_set.add(t_list[-1][0]-1)
    my_set.add(t_list[-1][1]-1)

q = []

for i in range(1, m+1):
    q.append([i])

while True:
    if len(q[0]) == n:
        break
    else:
        item = q.pop(0)
        if len(item) not in my_set:
            tmp = copy.deepcopy(item)
            tmp.append(item[-1])
            q.append(tmp)
        else:
            for i in range(item[-1], m+1):
                tmp = copy.deepcopy(item)
                tmp.append(i)
                q.append(tmp)

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)


### FIXED CODE ###

import itertools

t_list = []
n, m, q = map(int, input().split())
for i in range(q):
    t_list.append(list(map(int, input().split())))

q = []

for i in range(1, m+1):
    q.append(i)

ret = 0

for item in itertools.combinations_with_replacement(q, n):
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)