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

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(x):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

if __name__=="__main__":
    sol()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(j+1):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
                    p[k][j]=min(p[k][j],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

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

from itertools import combinations

n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = dict()
ver[()] = [abs(x) * p for x, _, p in xyp]
for cnt in range(1, n + 1):
    for pat in combinations(range(n), cnt):
        lines = [0]
        for i in pat:
            lines.append(xyp[i][0])

        costs = []
        for x, _, p in xyp:
            dist = INF
            for e in lines:
                dist = min(dist, abs(x - e))
            costs.append(dist * p)

        ver[pat] = costs

hor = dict()
hor[()] = [abs(y) * p for _, y, p in xyp]
for cnt in range(1, n + 1):
    for pat in combinations(range(n), cnt):
        lines = [0]
        for i in pat:
            lines.append(xyp[i][1])

        costs = []
        for _, y, p in xyp:
            dist = INF
            for e in lines:
                dist = min(dist, abs(y - e))
            costs.append(dist * p)

        hor[pat] = costs

ans = [INF] * (n + 1)
for i in range(3 ** n):
    now = i
    v = []
    h = []
    cnt = n
    for j in range(n):
        q, r = divmod(now, 3)
        if r == 1:
            v.append(j)
        elif r == 2:
            h.append(j)
        else:
            cnt -= 1
        now = q

    v = tuple(v)
    h = tuple(h)

    score = 0
    for ev, eh in zip(ver[v], hor[h]):
        score += min(ev, eh)

    ans[cnt] = min(ans[cnt], score)

print(*ans, sep="\n")


### FIXED CODE ###

import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")
### BUGGY CODE ###

import math
import bisect


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if (e % p != 0)]


arr = get_sieve_of_eratosthenes(100000)

arr_2 = [e for e in arr if int((e + 1) / 2) in arr]


Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr_2, l)
    right_ind = bisect.bisect_right(arr_2, r)
    print(right_ind - left_ind)

### FIXED CODE ###

import bisect
import math

def prime(n):
    for j in range(2, int(math.sqrt(n) + 1)):
        if n % j == 0:
            return False
    return True

lis = []
for i in range(3, 100000, 2):
    if prime(i) and prime((i + 1) / 2):
        lis.append(i)

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(lis, l)
    right_ind = bisect.bisect_right(lis, r)
    print(right_ind - left_ind)
### BUGGY CODE ###

n = int(input())
import numpy as np
s = input()
ans = 0
r, g, b = [], [], []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)
r, g, b = np.array(r), np.array(g), np.array(b)
tmp = []
for i in r:
    tmp.append(i)
    for j in g:
        tmp.append(j)
        for k in b:
            tmp.append(k)
            tmp.sort()
            if tmp[1] - tmp[0] != tmp[2] - tmp[1]:
                ans += 1
            tmp.remove(k)
        tmp.remove(j)
    tmp.remove(i)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
r, g, b = set(), set(), set()
for i in range(n):
    if s[i] == "R":
        r.add(i)
    elif s[i] == "G":
        g.add(i)
    else:
        b.add(i)

ans = len(r)*len(b)*len(g)
for i in r:
    for j in g:
        chk = j - i
        if chk + j in b:
            ans -= 1
        if i - chk in b:
            ans -= 1
        if (i + j)/2  in b:
            ans -= 1

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

[N, X, Y] = input().split()
N = int(N)
X = int(X)
Y = int(Y)
dist_list = []

for i in range(N):
    for j in range(i+1, N):
        dist_list.append(min(j - i, abs(i+1 - X) + abs(j+1 -Y) + 1))

for k in range(N-1):
    print(dist_list.count(k+1))



### FIXED CODE ###

N, X, Y = map(int, input().split())
dist_list = [0]*N

for i in range(N-1):
    for j in range(i+1, N):
        a = j - i
        b = abs(i+1 - X) + abs(j+1 -Y) + 1
        dist_list[min(a,b)] += 1

for k in range(N-1):
    print(dist_list[k+1])
### BUGGY CODE ###

import bisect
 
n = int(input())
d = sorted(list(map(int,input().split())))
m = int(input())
t = list(map(int,input().split()))
d.append(10**9+1)

flg = True
for i in range(m):
  index = bisect.bisect_left(d,t[i])
  if t[i] == d[index]:
    del d[index]
  else:
    flg = False
    break
 
print('YES' if flg else 'NO')

### FIXED CODE ###

import collections
 
n = int(input())
d = sorted(list(map(int,input().split())))
m = int(input())
t = list(map(int,input().split()))

cd = collections.Counter(d)
ct = collections.Counter(t)

flg = True
for k in ct.items():
  if k[1] > cd[k[0]]:
    flg = False

print('YES' if flg else 'NO')
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
*a, = map(int, input().split())

a = sorted(a)

for i in range(m):
    a[n-1] = a[n-1] // 2
    temp = a.pop()
    bisect.insort_left(a, temp)

'''
    left = 0
    right = n-2
    mid = 0
    while left < right:
        mid = (left + right) // 2
        if a[mid] > temp:
            right = mid - 1
            if right == left:
                a.insert(right+1, temp)
        elif a[mid] < temp:
            left = mid + 1
            if right == left:
                a.insert(right, temp)
        else:
            a.insert(right, temp)
            break
'''
    
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
*a, = map(int, input().split())

ans = []
for i in range(n):
    heapq.heappush(ans, -a[i])

for i in range(m):
    temp = -heapq.heappop(ans)
    heapq.heappush(ans, -(temp//2))

print(-sum(ans))
### BUGGY CODE ###

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

#dp[3N][N]
dp=[[0 for _ in range(N+1)] for _ in range(3*N+1)]
for i in range(1,3*N+1):
  for j in range(1,N+1):
    if i<j:
      break
    dp[i][j]=max(dp[i-1][j],alist[i-1]+dp[i-1][j-1])
#print(dp)

alist_rev=alist[::-1]
dp_rev=[[float("inf") for _ in range(N+1)] for _ in range(3*N+1)]
dp_rev[0][0]=0
for i in range(1,3*N+1):
  dp_rev[i][0]=0
  for j in range(1,N+1):
    if i<j:
      break
    dp_rev[i][j]=min(dp_rev[i-1][j],alist_rev[i-1]+dp_rev[i-1][j-1])
#print(dp_rev)

slist=[]
for i in range(3*N+1):
  slist.append(dp[i][N])
  
slist_rev=[]
for i in range(3*N+1):
  slist_rev.append(dp_rev[-i-1][N])
  
#print(slist)
#print(slist_rev)

answer=-float("inf")
for i in range(N,2*N+1):
  score=slist[i]-slist_rev[i]
  answer=max(score,answer)
  
print(answer)

### FIXED CODE ###

import heapq
N=int(input())
alist=list(map(int,input().split()))

sum1=0
hq1=[]
for i in range(N):
  sum1+=alist[i]
  heapq.heappush(hq1,alist[i])
sum1_list=[sum1]
for i in range(N,2*N):
  heapq.heappush(hq1,alist[i])
  min_s1=heapq.heappop(hq1)  
  sum1+=alist[i]-min_s1
  sum1_list.append(sum1)
#print(sum1_list)  
  
alist_rev=alist[::-1]  
sum2=0
hq2=[]
for i in range(N):
  sum2+=alist_rev[i]
  heapq.heappush(hq2,-alist_rev[i])
sum2_list=[sum2]
for i in range(N,2*N):
  heapq.heappush(hq2,-alist_rev[i])
  max_s2=-heapq.heappop(hq2)
  sum2+=alist_rev[i]-max_s2
  sum2_list.append(sum2)
sum2_list.reverse()
#print(sum2_list)  

answer=-float("inf")
for i in range(N+1):
  answer=max(answer,sum1_list[i]-sum2_list[i])

print(answer)
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]
count = 0
for i in range(n-1):
    si = [x for x in s[i]]
    si = Counter(si)
    for j in range(i+1, n):
        sj = [x for x in s[j]]
        if si == Counter(sj):
            count += 1
print(count)


### FIXED CODE ###

n = int(input())
s = [[x for x in input()] for _ in range(n)]
ans = 0
d = {}
for i in range(n):
    key = "".join(sorted(s[i]))
    if key in d:
        ans += d[key]
        d[key] += 1
    else:
        d[key] = 1

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

n = int(input())
a = [int(i) for i in input().split()]
prd = 1
if 0 in a:
  print(0)
  exit()
for i in range(n):
  prd*=a[i]
if prd > 10**18:
  print(-1)
else:
  print(prd)

### FIXED CODE ###

import sys

n = int(input())
a = [int(i) for i in input().split()]
prd = 1
if 0 in a:
  print(0)
  sys.exit()
for i in range(n):
  prd*=a[i]
  if prd > 10**18:
    print(-1)
    sys.exit()
print(prd)
### BUGGY CODE ###

import math
import sys

sys.setrecursionlimit(10 ** 9)
n = int(input())


def make_prime_list(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0  # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]


prime_list = make_prime_list(math.floor(math.sqrt(10 ** 7 + 1)))


def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count
        if num != 1:
            divisor_num *= 2
    return divisor_num


# def solve(n, acc):
#   if (n == 1):
#     return acc
#   else:
#     return solve(n - 1, search_divisor_num_1(n) * n + acc)

ans = 1
while n > 1:
  ans += search_divisor_num_1(n) * n
  n = n - 1

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
  tail = (n // i) * i
  ans += (i + tail) * (tail // i) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
ret = 0
for i in range(N):
  ret += i
print(ret)

### FIXED CODE ###

N = int(input())
ret = N * (N-1) // 2
print(ret)
### BUGGY CODE ###

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

P, Y = [], []
dic = {}
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    if p in dic:
        dic[p].append(y)
    else:
        dic[p] = [y]

result = []
for n in range(M):
    result.append(1)
    if not P[n] in dic:
        continue
    for i in range(n):
        if P[n] == P[i]:
            if Y[n] > Y[i]:
                result[n] += 1
            else:
                result[i] += 1


for x, y in zip(P, result):
    x, y = str(x), str(y)
    print('0'*(6-len(x))+x+'0'*(6-len(y))+y)


### FIXED CODE ###

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

P, Y = [], []
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)

result = [1] * M
citys = [[] for _ in range(N)]

for i, n in enumerate(P):
    citys[n-1].append([Y[i], i])

for c in citys:
    
    c.sort()
    for i, k in enumerate(c):
        result[k[1]] += i



for x, y in zip(P, result):
    x, y = str(x), str(y)
    print('0'*(6-len(x))+x+'0'*(6-len(y))+y)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A_set = list(set(A))
result = []
for i in range(len(A_set)):
  if A.count(A_set[i])%2!=0:
    if i in result:
      continue
    result.append(A_set[i])
print(len(result))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
dict = {}
for i in A:
  if i not in dict:
    dict[i] = 1
  else:
    dict[i] += 1
print(len([1 for i in dict.values() if i%2!=0]))
### BUGGY CODE ###

n=int(input())
s=input()
def chk(x):
  x=str(x).zfill(3)
  res=False
  cur=0
  xx=x[0]
  for i in range(n):
    ss=s[i]
    if cur<2 and xx==ss:
      cur+=1
      xx=x[cur]
    elif xx==ss:
      res=True
      break
  return res

ans=0
for i in range(1000):
  if chk(i):
    ans+=1
print(ans)  


### FIXED CODE ###

n=int(input())
s=input()
inf=float("inf")
A=[[inf]*10 for _ in range(n+1)]
for i in reversed(range(n)):
  ss=s[i]
  for j in range(10):
    if j==int(ss):
      A[i][j]=i
    else:
      A[i][j]=A[i+1][j]
ans=0
for x in range(1000):
  x=str(x).zfill(3)
  cur=0
  for xx in x:
    xx=int(xx)
    cur=A[cur][xx]+1
    if cur==inf:
      break
  if cur!=inf:
    ans+=1
print(ans)
### BUGGY CODE ###

from sys import stderr

def reads():
  return [int(x) for x in input().split()]

INF = 1 << 63

N, M, K = reads()
A = reads()

dp = A
for j in range(2, K+1):
  deq = [0] * N; l = r = 0
  q = [-INF] * N
  for i in range(N):
    # pop
    while l < r and deq[l] < i-M:
      l += 1
    # max
    q[i] = j * A[i] + (dp[deq[l]] if l < r else -INF)
    # append
    while l < r and dp[deq[r-1]] <= dp[i]:
      r -= 1
    deq[r] = i; r += 1
  dp = q

print(max(dp))


### FIXED CODE ###

from sys import stderr

def reads():
  return [int(x) for x in input().split()]

N, M, K = reads()
A = reads()

dp = [[0] * N, list(A)]
deq = [0] * N
for j in range(2, K+1):
  l = r = 0
  b = j & 1
  prev = dp[1-b]; curr = dp[b]
  for i in range(N):
    # pop
    while l < r and deq[l] < i-M:
      l += 1
    # max
    curr[i] = (j * A[i] + prev[deq[l]]) if (i >= j-1 and l < r) else 0
    # append
    while l < r and prev[deq[r-1]] <= prev[i]:
      r -= 1
    deq[r] = i; r += 1

print(max(dp[K & 1]))
### BUGGY CODE ###

n, k = map(int, input().split())
h = [0] + list(map(int, input().split()))
inf = 10**5
dp = [inf]*(n+1)
dp[1] = 0
dp[2] = abs(h[1] - h[2])
for i in range(3, n+1):
    dp[i] = min(
        [dp[i-j] + abs(h[i-j] - h[i]) for j in range(1, min(k, i)+1)]
    )
print(dp[n])

### FIXED CODE ###

N, K= map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*(N+1)
for i in range(1, N):
    dp[i+1] = min(
        [
            abs(h[i]-h[i-k]) + dp[i+1-k]
            for k in range(1, min(K, i)+1)
        ]
    )
print(dp[N])
### BUGGY CODE ###

N = int(input())
X = [int(i) for i in input().split()]

sortedX = X[:]
sortedX.sort()
lenX = len(X)

for i in X:
    if sortedX.index(i) > int(lenX/2) - 1:
        print(sortedX[int(lenX/2)-1])
    else:
        print(sortedX[int(lenX/2)])



### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]

sortedX = X[:]
sortedX.sort()
lenX = len(X)

for i in X:
    if i > sortedX[int(lenX/2) - 1]:
        print(sortedX[int(lenX/2)-1])
    else:
        print(sortedX[int(lenX/2)])
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [int(i) for i in input().split()]
A = np.array([A[i] - i - 1 for i in range(N)])
ans = 0
for i in range(N):
    if i == 0:
        ans = np.sum(np.abs(A - np.ones(N) * A[i]))
    else:
        ans = min(ans, np.sum(np.abs(A - np.ones(N) * A[i])))
print(int(ans))


### FIXED CODE ###

N = int(input())
if N == 1:
    print(0)
    exit()
A = [int(i) for i in input().split()]
A = [A[i] - i - 1 for i in range(N)]
A.sort()
if N == 2:
    print(abs(A[0] - A[1]))
    exit()

sum_A = [0, 0]
for i in range(N):
    sum_A[0] += abs(A[i] - A[N // 2])
sum_2 = 0
for i in range(N):
    sum_A[1] += abs(A[i] - A[N // 2 + 1])
print(min(sum_A))
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
vals = []
for i in range(n-k+1):
    vals.append(sum(p_list[i:i+k]))
        
print((max(vals) + k )/2)

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))

for i in range(n):
    p_list[i] = (1 + p_list[i]) / 2

wa = sum(p_list[0:k])
ans = wa

for j in range(n-k):
    wa = wa + p_list[j+k] - p_list[j]
    ans = max(ans, wa)
    
print(ans)
### BUGGY CODE ###

n = int(input())
L =sorted([int(i) for i in input().split()],reverse=True)

count=0
for i in range(0, len(L),1):
  for j in range(i+1,len(L),1):
    for k in range(j+1,len(L),1):
      if (L[j] + L[k] > L[i]):
        count +=1
print(count)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    S = input().rstrip()
    T = [-1] * N

    sToIndex = defaultdict(int)
    now = 1

    for i, s in enumerate(S):
        if not s in sToIndex:
            T[i] = now
            sToIndex[s] = now
            now += 1
        else:
            T[i] = sToIndex[s]

    cumT = [0] * (N + 1)
    for i in range(1, N + 1):
        cumT[i] = cumT[i - 1] + T[i - 1]

    cumTList = []
    for left in range(N):
        for right in range(left + 1, N + 1):
            cumTList.append((cumT[right] - cumT[left], left, right))

    matchList = defaultdict(list)
    for v, l, r in cumTList:
        matchList[v].append((l, r))

    ans = 0
    for v, match in matchList.items():
        for i in range(len(match)):
            for j in range(i + 1, len(match)):
                l1, r1 = match[i]
                l2, r2 = match[j]
                if l2 < r1:
                    continue
                if T[l1: r1] == T[l2: r2]:
                    ans = max(ans, r1 - l1)

    print(ans)

sol()

### FIXED CODE ###

from collections import deque

N = int(input())
S = input()

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if 0 <= y - i and x - i != p[y - i]:
            print(x - i)
            break
        if y + i < n and x + i != p[y + i]:
            print(x + i)
            break
        i = i + 1

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if y - i < 0:
            print(p[0] - 1)
            break
        elif x - i != p[y - i]:
            print(x - i)
            break
        if n <= y + i:
            print(p[n - 1] + 1)
            break
        elif x + i != p[y + i]:
            print(x + i)
            break
        i = i + 1
### BUGGY CODE ###

import math
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
ans = 0
def fac(a, b):
  a = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
  return a % p
for h in range(H - A):
  ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
print(ans % p)

### FIXED CODE ###

import math
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
F = [1 for i in range(H + W + 1)]
for i in range(1, H + W + 1):
  F[i] = F[i - 1] * i % p
def fac(a, b):
  a = F[a + b] * pow(F[a], p - 2, p) * pow(F[b], p - 2, p)
  return a % p
if H - A < B:
  ans = 0
  for h in range(H - A):
    ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
else:
  ans = fac(H - 1, W- 1)
  for w in range(B):
    ans -= fac(H - A - 1, w) * fac(A - 1, W - w - 1) % p
print(ans % p)
### BUGGY CODE ###

from itertools import combinations
import collections
n = int(input())
s = [''.join(sorted(input())) for i in range(n)]

c = 0
r = collections.Counter(s)
for k, v in r.items():
    if v > 1:
        c += len(list(combinations(range(v), 2)))

print(c)

### FIXED CODE ###

import collections

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]

c = 0
r = collections.Counter(s)
for v in r.values():
    c += (v * (v - 1)) // 2

print(c)