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

import math
n,k=map(int, input().split())
p=list(map(int, input().split()))
max = 0

for i in range(n):
    if p[i] % 2 == 0:
        p[i] = (p[i] + 1) * (p[i] / 2) /p[i]
    else:
        p[i] = ((p[i] + 1) * math.floor(p[i] / 2) + math.ceil(p[i] / 2))  /p[i]

for i in range(n - k + 1):
    tmp = 0
    for j in range(k):
        tmp = tmp + p[i + j]
    if max < tmp:
        max = tmp

print(max)

### FIXED CODE ###

import math
n,k=map(int, input().split())
p=list(map(int, input().split()))

for i in range(n):
    if p[i] % 2 == 0:
        p[i] = (p[i] + 1) * (p[i] / 2) /p[i]
    else:
        p[i] = ((p[i] + 1) * math.floor(p[i] / 2) + math.ceil(p[i] / 2))  /p[i]

tmp = 0
for j in range(k):
    tmp = tmp + p[j]

max = tmp

for i in range(n - k):
    tmp = tmp - p[i] + p[i + k]
    if max < tmp:
        max = tmp

print(max)
### BUGGY CODE ###


import itertools


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
moded_li = []
for i in li:
    ans = i % MOD_NUMBER
    if ans != 0:
        moded_li.append(ans)
ans = 0
for i in itertools.combinations(moded_li, 2):
    # print(i)
    ans += i[0]*i[1]
print(ans % MOD_NUMBER)


### FIXED CODE ###


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
nizyo_list = [i**2 for i in li]
ans = (sum(li)**2-sum(nizyo_list))//2
print(ans % MOD_NUMBER)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sa = sorted(a)
r, ans = 0, 0
for l in range(n):
    cnt = 1
    r = l + 1
    while r < n and abs(sa[r] - sa[l]) <= 2:
        cnt += 1
        r += 1

    ans = max(ans, cnt)
    if l == r:
        r += 1

print(ans)


### FIXED CODE ###

n = int(input())
b = [0] * (10 ** 5 + 1)
a = list(map(int, input().split()))
for i in a:
    b[i] += 1
    if i < 10 ** 5:
        b[i + 1] += 1
    if i > 0:
        b[i - 1] += 1

print(max(b))
### BUGGY CODE ###

S = [int(_) for _ in input()]
length = 0
x =0
flag = True
if(len(S) == 1):
    flag = False
while(flag):
    x += 1

    if(S[x]+S[x-1] == 1):
        S.pop(x)
        S.pop(x-1)
        length += 2
        x=0
   
    if(x >= len(S)-1):
        break

print(length)
        

### FIXED CODE ###

S = [int(_) for _ in input()]
length = len(S)
temp = [S[0]]
for x in S[1:]:
    if(len(temp) == 0):
        temp.append(x)
    elif( temp[-1] == x):
        temp.append(x)
    else:
        temp.pop(-1)
print(length-len(temp))
### BUGGY CODE ###

# Using BFS
from collections import defaultdict, deque
import sys


def input():
    return sys.stdin.readline()


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.append(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = deque()
        push(i, 0, dist, q)
        while len(q) != 0:
            v = q.popleft()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# Using BFS
from collections import defaultdict, deque
import sys


def input():
    return sys.stdin.readline()


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.append(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = deque()
        push(i, 0, dist, q)
        while len(q) != 0:
            v = q.popleft()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


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

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import copy
N=int(input())
A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1

playerlst=set([i for i in range(N)])

count=0
while playerlst:
    lst=copy.copy(playerlst)
    flag=0
    while lst:
        p=lst.pop()
        p2=A[p][-1]
        if p2 in lst and A[p2][-1]==p:
            flag=1
            A[p].pop()
            A[p2].pop()
            lst.remove(p2)
            if not A[p]:
                playerlst.remove(p)
            if not A[p2]:
                playerlst.remove(p2)
    if not flag:
        print(-1)
        exit()
    count+=1
print(count)


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import copy
N=int(input())
A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1

playerlst=set([i for i in range(N)])

count=0
nlst=copy.copy(playerlst)
while playerlst:
    flag=0
    lst=set()
    playedlst=set()
    while nlst:
        p=nlst.pop()
        if not p in lst and p in playerlst:
            p2=A[p][-1]
            if not p2 in lst and p2 in playerlst:
                if A[p2][-1]==p:
                    flag=1
                    A[p].pop()
                    A[p2].pop()
                    lst.add(p)
                    lst.add(p2)
                    if p2 in nlst:
                        nlst.remove(p2)
                    playedlst.add(p)
                    playedlst.add(p2)
                    if not A[p]:
                        playerlst.remove(p)
                    if not A[p2]:
                        playerlst.remove(p2)
    if not flag:
        print(-1)
        exit()
    count+=1
    nlst=copy.copy(playedlst)
print(count)
### BUGGY CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[n-1]=0
else:
  A[n-1]=1
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

### FIXED CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid
### BUGGY CODE ###

import numpy as np
from numba import njit


n = int(input())
a = np.array(list(map(int, input().split())))
ans = 0

@njit
def check(ans):
  for i in range(n):
    temp = a[i]
    count = np.count_nonzero(temp%a==0)
    if count == 1:
      ans += 1
  return ans

ans = check(ans)
print(ans)

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#@njit
def slove(A):
  count = np.zeros(10**6 + 10, np.int32)
  for x in A:
    if count[x] > 1:
      continue
    count[::x] += 1
  ret = 0
  for x in A:
    ret += count[x] == 1
  return ret

A = np.array(read().split(), np.int32)[1:]

print(slove(A))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N,d,a = map(int,readline().split())

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
  return get(data1,r-1)*(r-1)+get(data0,r-1)-get(data1,l-1)*(l-1)-get(data0,l-1)

xh = []
for _ in range(N):
    x,h = map(int,readline().split())
    xh.append((x,h))

xh = sorted(xh)
xl = [x for x,h in xh]

for i in range(N):
    add(i+1, i+2, xh[i][1])

import bisect,math

ans = 0
for i in range(N):
    hp = query(i + 1, i + 2)
    #print(data0,data1,hp)    
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect_right(xl, xl[i] + 2*d)
        add(i+1, idx+1, -damage)
print(ans)

### FIXED CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  n, d, a = [int(i) for i in input().split()]
  chk = []
  for i in range(n):
    x, h = [int(i) for i in input().split()]
    chk.append((x, 0, h))

  from heapq import heapify, heappop, heappush
  heapify(chk)
  atk_cnt = 0; ans = 0
  while chk:
    x, t, h = heappop(chk)
    if t == 0:
      if atk_cnt * a >= h:
          continue
      remain = h - atk_cnt * a
      new_atk = (remain - 1) // a + 1
      heappush(chk, (x + 2 * d, 1, new_atk))
      ans += new_atk
      atk_cnt += new_atk
    else:
      atk_cnt -= h
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections
a = collections.Counter(A)
b = []
for i in range(len(a)):
    if a.most_common()[i][1] >= 2:
        b.append(a.most_common()[i])
    else:
        break
b.sort(reverse=True)
if len(b) >= 1 and b[0][1] >= 4:
    print(b[0][0] ** 2)
elif len(b) >= 2:
    print(b[0][0] * b[1][0])
else:
    print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections
a = collections.Counter(A)
b = []
for i, j in a.items():
    if j >= 2:
        b.append([i,j])
b.sort(reverse=True)
if len(b) >= 1 and b[0][1] >= 4:
    print(b[0][0] ** 2)
elif len(b) >= 2:
    print(b[0][0] * b[1][0])
else:
    print(0)
### BUGGY CODE ###

s_l = list(input())
n = len(s_l)

ans = 0
flag = -1
for i in range(n-1,-1,-1):
    for j in range(i,-1,-1):
        if flag > 0:
            flag -= 1
            continue
        val = int(''.join(s_l[j:i+1]))
        if val%2019 == 0 and val != 0:
            ans += 1
            flag = 4
        else:
            flag = -1

print(ans)

### FIXED CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

ans = 0
for val in dp_dict.values():
    ans += val*(val-1)//2

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

#K : XYZそれぞれは、0以上K以下
#S : X+Y+Zの合計値を示すS

K,S = map(int,input().split())

X=Y=Z=0
result = 0
while(X<=S):
    while(X+Y<=S):
        Z = S-X-Y
        # print("X,Y,Z",X,Y,Z)
        if X+Y+Z == S:
            if X<=K and Y<=K and Z<=K :
                result+=1 
        # Z=X+Y-S
        # if X+Y+Z==S:
        #     result +=1
        # while(Z<=K):
        #     if X+Y+Z<S:
        #         pass
        #     elif X+Y+Z==S:
        #         result +=1
        #     else:
        #         break
        #     Z+=1
        # if X+Y+Z>S:
        #     break
        if Y<=K:
            Y+=1
        else:
            break
    Y=0
    X+=1
print(result)

### FIXED CODE ###

#K : XYZそれぞれは、0以上K以下
#S : X+Y+Zの合計値を示すS

K,S = map(int,input().split())

X=Y=Z=0
result = 0
for x in range(K+1):
    for y in range ( K+1 ):
        if 0 <= S-X-Y <=K:
            result +=1
        # Z = S-X-Y
        # # print("XYZ",X,Y,Z)
        # if X+Y+Z == S:
        #     if  Z<=K :
        #         result+=1 
        Y+=1
    Y=0
    X+=1

print(result)
### BUGGY CODE ###

from math import factorial

n = int(input())
a = list(map(int, input().split()))
s = [0]
s.extend([sum(a[0:i+1]) for i in range(n)])
s_uniq = list(set(s))
result = 0

for s_uniq_i in s_uniq:
    count = s.count(s_uniq_i)
    if count >= 2:
        result += int( factorial(count) / (factorial(count-2) * factorial(2)) )

print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

print(result)
### BUGGY CODE ###

def dfs(count, ans, ll):
    if count == 2:
        for cc in c:
            cccc = ans + cc
            if cccc is not None:
                ll.append(cccc)
    if count == 1:
        for bb in b:
            bbbb = dfs(count+1, ans+bb, ll)
            if bbbb is not None:
                ll.append(bbbb)
    if count == 0:
        for aa in a:
            aaaa = dfs(count+1, ans+aa, ll)
            if aaaa is not None:
                ll.append(aaaa)
        return ll

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
aaa = []
ans = dfs(0, 0, aaa)
ans.sort()
ans = list(reversed(ans))
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M, P = map(int, input().split())
G = []
G_append = G.append

g = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G_append((A, B, -C + P))
    g[A].append(B)

d = [INF] * (N + 1) #最短距離を記録しておくリスト
d[1] = 0
def find_negative_loop1(): #負の閉路が存在するかを確認
    for i in range(N):
        for j in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                #頂点の回数と同じだけループを回しても更新が起きる-->負の閉回路が存在
                if i == N-1:
                    return True #Trueの時, 負の閉路が存在
    return False #Falseの時, 負の閉路が存在しない

def find_negative_loop2(): #負の閉路が存在するかを確認
    check = [False] * (N + 1)
    for _ in range(N):
        for j in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                check[e[1]] = True
    return check[N]

#呼び出しスタート地点を入れる
if find_negative_loop1():
    if find_negative_loop2():
        print (-1)
    else:
        print (max(0, -d[N]))
else:
    print (max(0, -d[N]))





### FIXED CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == 2 * N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

print (max(0, -d[N - 1]))
### BUGGY CODE ###

from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v].items(): dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
V = list(range(N))
E = {v: {} for v in V}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c

dist = floyd_warshall(V, E)
E_charge = {v: {} for v in V}
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge = floyd_warshall(V, E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)

### FIXED CODE ###

from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(E)

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))

exp = [(x+1)*0.5 for x in p]

summed = []
for i in range(N-K+1):
    summed.append(sum(exp[i:i+K]))

print(max(summed))

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))

exp = [(x+1)*0.5 for x in p]

sums = []
sums.append(0.0)
for i in range(1,N+1):
    sums.append(sums[i-1]+exp[i-1])

#print(sums)
ans = 0.0
for i in range(N-K+1):
    if ans < sums[i+K] - sums[i]: ans = sums[i+K] - sums[i];

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

import numpy as np
A, B, Q=map(int, input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]
x=[int(input()) for _ in range(Q)]

def f(nums, a):
  if a<=nums[0]:
    return nums[0]-a
  if nums[-1]<=a:
    return a-nums[-1]
  tmp=np.searchsorted(nums, a, side='left')
  return min(a-nums[tmp-1], nums[tmp]-a)

for i in range(Q):
  out=2*10**10
  if x[i]<=s[0]:
    s2=s[0]
    out=min(out, s2-x[i]+f(t, s2))
  elif s[-1]<=x[i]:
    s1=s[-1]
    out=min(out, x[i]-s1+f(t, s1))
  else:
    tmp=np.searchsorted(s, x[i], side='left')
    s1=s[tmp-1]
    out=min(out, x[i]-s1+f(t, s1))
    s2=s[tmp]
    out=min(out, s2-x[i]+f(t, s2))
    
  if x[i]<=t[0]:
    t2=t[0]
    out=min(out, t2-x[i]+f(s, t2))
  elif t[-1]<=x[i]:
    t1=t[-1]
    out=min(out, x[i]-t1+f(s, t1))
  else:
    tmp=np.searchsorted(t, x[i], side='left')
    t1=t[tmp-1]
    out=min(out, x[i]-t1+f(s, t1))
    t2=t[tmp]
    out=min(out, t2-x[i]+f(s, t2))
    
  print(out)

### FIXED CODE ###

import bisect

A, B, Q=map(int, input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]
x=[int(input()) for _ in range(Q)]

st=[0]*A
ts=[0]*B

for i in range(A):
  tmp=bisect.bisect_left(t, s[i])
  if tmp==0:
    st[i]=t[0]-s[i]
  elif tmp==B:
    st[i]=s[i]-t[-1]
  else:
    st[i]=min(s[i]-t[tmp-1], t[tmp]-s[i])
    
for i in range(B):
  tmp=bisect.bisect_left(s, t[i])
  if tmp==0:
    ts[i]=s[0]-t[i]
  elif tmp==A:
    ts[i]=t[i]-s[-1]
  else:
    ts[i]=min(t[i]-s[tmp-1], s[tmp]-t[i])

for i in range(Q):
  cand=set()
  tmp=bisect.bisect_left(s, x[i])
  if tmp>0:
    cand.add(x[i]-s[tmp-1]+st[tmp-1])
  if tmp<A:
    cand.add(s[tmp]-x[i]+st[tmp])
    
  tmp=bisect.bisect_left(t, x[i])
  if tmp>0:
    cand.add(x[i]-t[tmp-1]+ts[tmp-1])
  if tmp<B:
    cand.add(t[tmp]-x[i]+ts[tmp])
    
  print(min(cand))
### BUGGY CODE ###

import math, sys

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

d = math.floor(M/N)

for i in range(d):
	if M%(d-i) == 0:
		print(d-i)
		sys.exit()

### FIXED CODE ###

import math, sys, random

N, M = list(map(int,input().split()))
# N, M = 1111, 1000000000

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

d = int(math.floor(M/N))

if M%N == 0:
	print(d)
	sys.exit()

i = 0
f = False
while True:
	if M%(N+i+1) == 0:
		print(int(M/(N+i+1)))
		sys.exit()
	i += 1
	if i == 100000 and is_prime(M):
		print(1)
		sys.exit()
### BUGGY CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
SUM = [0]
for i in range(N):
    a = A[i]%M
    SUM.append(SUM[-1]+a)
ans = 0
for l in range(N):
    for r in range(l+1,N+1):
        if (SUM[r] - SUM[l])%M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
D = {0:1}
a = 0
ans = 0
for i in range(N):
    a = (a+A[i])%M
    ans += D.get(a,0)
    D[a] = 1 + D.get(a,0)
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
n = int(input())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i+1] = inp
    new = tuple(sorted([i+1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    new_ls = []
    for i, j in battle_dict.items():
        if len(j) > 0:
            new_ls.append(tuple(sorted([i, j[0]])))
    cur_stage.update(new_ls)
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)