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

def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
S.sort()
T.sort()
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort()
for _ in range(Q):
    x = int(input())
    print(near2(x,D))



### FIXED CODE ###

def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
D2 = [d for d, _ in D]
for _ in range(Q):
    x = int(input())
    print(near2(x,D2))
### BUGGY CODE ###


from functools import lru_cache


a = int(input())
b = input()

@lru_cache(maxsize=None)
def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))


### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
### BUGGY CODE ###

import sys
from itertools import permutations

def warshall_floyd(d):
    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])
    return d


def main():
    input = sys.stdin.readline
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))

    INF = 10**9
    A = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        A[a-1][b-1] = c
        A[b-1][a-1] = c

    A = warshall_floyd(A)

    ans = INF
    for root in permutations(r):
        cur = 0
        for i in range(R-1):
            s, g = root[i] - 1, root[i+1] - 1
            cur += A[s][g]

        ans = min(ans, cur)

    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations


def main():
    input = sys.stdin.readline
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))

    INF = 10**9
    A = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        A[a-1][b-1] = c
        A[b-1][a-1] = c

    D = np.array(A, dtype=int)
    G = floyd_warshall(D)

    """
    ans = INF
    for start in r[:2]:
        passed = [start]
        temp_ans = 0
        while len(passed) < len(r):
            cur = INF
            next_start = -1
            for dest in r:
                if dest in passed:
                    continue

                if A[start-1][dest-1] < cur:
                    next_start = dest
                    cur = A[start-1][dest-1]

            passed.append(next_start)
            start = next_start
            temp_ans += cur

        ans = min(ans, temp_ans)
    """

    ans = INF
    for root in permutations(r):
        cur = 0
        for i in range(R-1):
            s, g = root[i] -1, root[i+1] - 1
            cur += G[s][g]

        ans = min(ans, cur)

    return int(ans)


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

from scipy.sparse import *
from itertools import *
 
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
  
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
#Co = csgraph.floyd_warshall(csr_matrix(route_list))
Co = warshall_floyd(route_list)
  
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

### FIXED CODE ###

import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10**9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

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

from collections import Counter
s = input()[::-1]
mod = 2019

x = [0]

for i, j in enumerate(s):
    x.append((x[-1] + int(j) * pow(10,i))%mod)

C = Counter(x)
ans = 0

for v in C.values():
    ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()[::-1]
mod = 2019

x = [0]

for i, j in enumerate(s):
    x.append((x[-1] + int(j) * pow(10,i, mod))%mod)

C = Counter(x)
ans = 0

for v in C.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import mul
from collections import deque

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

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

B = deque(A[:K])

C = reduce(mul,B)

for i in range(K,N):
  B.popleft()
  B.append(A[i])
  D = reduce(mul,B)
  if C < D:
    print('Yes')
  else:
    print('No')
  C = D

### FIXED CODE ###

from collections import deque

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

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

B = deque(A[:K])

for i in range(K,N):
  if B.popleft() < A[i]:
    print('Yes')
  else:
    print('No')    
    
  B.append(A[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  print(a.count(i+1))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
All = Counter(a)
for i in range(1,n+1):
    try:
        print(All[i])
    except:
        print(0)
### BUGGY CODE ###

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

ans = 1
for item in a:
  ans = ans * item
  if ans > 1000000000000000000:
    ans = -1

print(ans)


### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  
  if 0 in A:
    print(0)
    return
  
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
  
main()
### BUGGY CODE ###

N = int(input())
P = [int(n) for n in input().split()]
c = 0
o = range(1, N+1)[::-1]
if o==P:
    print(N)
else:
    while P:
        r = min(P)
        P = P[:P.index(r)]
        c += 1
    print(c)


### FIXED CODE ###

N = int(input())
P = [int(n) for n in input().split()]
c = 0
curr = 2*10**5+1
for p in P:
    if p < curr:
        curr = p
        c += 1
print(c)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
MAX_NUM = 10 ** 9 + 7
def func(M):
  res = []
  i, c = 2, 0
  while True:
    if M % i == 0:
      M = M / i
      c+=1
    else:
      if c > 0:
        res.append(c)
        c = 0
      i += 1
      if M==1:
        break
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % MAX_NUM
print(ans)

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
def func(M):
  res = []
  i = 2
  while i * i <= M:
    c=0
    while M % i == 0:
      M /= i
      c += 1
    if c > 0:
      res.append(c)
    i += 1
  if M > 1:
    res.append(1)
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % mod
print(ans)
### BUGGY CODE ###

import sys


def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p
    
    
def comb(n, k, p):
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


x, y = map(int, input().split())

w = (x + y) / 3
b = (- x + 2*y) // 3

if w.is_integer():
    w = int(w)
else:
    print(0)
    sys.exit()

a = min(b, w-b)
ans = comb(w, a, 10**9+7)
print(ans)


### FIXED CODE ###

import sys
x, y = map(int, input().split())

if (x + y) % 3 != 0:
    print(0)
    sys.exit()

mod = 10**9 + 7
n = (x+y) // 3
a = min(
    (2 * x - y) // 3, (2 * y - x) // 3
)


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


N = max(x, y)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

ans = cmb(n, a, mod)
print(ans)
### BUGGY CODE ###

x,y = map(int,input().split())
i = 1
if x == y:
  print(-1)
else:
  while True:
    if (i*x)%y != 0:
      print(i*x)
    else:
      i += 1

### FIXED CODE ###

x,y = map(int,input().split())
if x%y == 0:
  print(-1)
else:
  print(x)
### BUGGY CODE ###

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


mod = 10**9+7
n = int(input())
a = tuple(map(int,input().split()))

pr = primes(10**6+1)

d = dict()

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if p in d:
            if c > d[p]:d[p] = c
        elif c != 0:
            d[p] = c


lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

res = 0
for e in a:
    res = (res + pow(e,mod-2,mod))%mod
print(res*lcm%mod)



### FIXED CODE ###

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)


mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))

l = a[0]
for e in a:
    l = lcm(l,e)

a_sum = 0
for e in a:
    a_sum = (a_sum + pow(e,mod-2,mod))%mod

print((l%mod)*a_sum%mod)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
from collections import Counter
for i in range(n):
	count = 0
	C = Counter(A[:i] + A[i+1:])
	for v in C.values():
		count += v * (v - 1) // 2
	print(count)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
from collections import Counter
C = Counter(A)
count = 0
for v in C.values():
	count += v * (v - 1) // 2
for a in A:
	x = C[a]
	print(count - (x * (x - 1) // 2) + ((x - 1) * (x - 2) // 2))
### BUGGY CODE ###

import sys

# def add(x,y):
# 	return x+y

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	first = 0
	second = 0
	second_list = []
	scnd_acml = []
	for L in range(N):
		if P[L]>first:
			second = first
			first = P[L]
		elif P[L]>second:
			second = P[L]

		if L!=0:
			x = x+second
			second_list.append(second)
			scnd_acml.append(0)
			scnd_acml = list(map(lambda x:x+second, scnd_acml))

	for L in range(1,N-1):
		first = 0
		second = 0
		for i in range(N-L):
			ind = L+i
			if P[ind]>first:
				second = first
				first = P[ind]
			elif P[ind]>second:
				second = P[ind]

			if second==second_list[ind-1]:
				x = x+scnd_acml[ind-1]
				break
			else:
				x = x+second
		

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

from time import time
from fractions import gcd
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    s=lcm(s,t)
    if time()-start>.6:
        break
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

def resolve():
    s = input()
    k = int(input())
    l = len(s)
    subs = []
    for i in range(l):
        for j in range(i + 1, l + 1):
            sub = s[i:j]
            subs.append(sub)
    print(sorted(set(subs))[k - 1])


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    s = input()
    k = int(input())
    l = len(s)
    subs = []
    for i in range(l):
        for j in range(i + 1, i + k + 1):
            sub = s[i:j]
            if sub not in subs:
                subs.append(sub)
    print(sorted(set(subs))[k - 1])


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

N, P = map(int, input().split())
S = input()
count = [0] * P
ans = 0
for d in S:
    d = int(d)
    count[0] += 1
    ncount = [0] * P
    for i in range(P):
        ni = (i * 10 + d) % P
        ncount[ni] += count[i]
    count = ncount
    ans += count[0]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    factor = 10
    for i in range(N)[::-1]:
        U[i] = (S[i] * factor + U[i+1]) % P
        factor = factor * 10 % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)
### BUGGY CODE ###

from collections import deque

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]

c = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)

s = 0
for i in range(n):
    if len(c[i]) > s:
        s = i

e = [0] * n
l = [0] * (n-1)
q = deque()
q.append((s, 0))
while q:
    f, v = q.pop()
    e[f] = 1
    j = 1
    for i in c[f]:
        if e[i] == 0:
            if j == v:
                j += 1
            q.appendleft((i, j))
            l[ab.index([min(f, i)+1, max(f, i)+1])] = j
            j += 1

print(max(l))
for i in l:
    print(i)

### FIXED CODE ###

def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

    n = int(readline())
    ab = [list(map(int, readline().split())) for _ in range(n-1)]

    l = [[] for _ in range(n+1)]
    for a, b in ab:
        l[a].append(b)
        l[b].append(a)

    parents = [-1] * (n+1)
    order = []
    q = deque()
    q.append(1)
    while q:
        c = q.pop()
        order.append(c)
        for i in l[c]:
            if i == parents[c]:
                continue
            parents[i] = c
            q.append(i)
    
    color = [-1] * (n+1)
    for i in order:
        ng = color[i]
        c = 1
        for j in l[i]:
            if j == parents[i]:
                continue
            if c == ng:
                c += 1
            color[j] = c
            c += 1
    
    ans = []
    for a, b in ab:
        if a == parents[b]:
            ans.append(color[b])
        else:
            ans.append(color[a])

    print(max(ans))
    print('\n'.join(list(map(str, ans))))

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

from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    for i in range(len(S)):
        _, mod = divmod(int_S % (10**(i+1)), 2019)
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

n=int(input())
D=[int(i) for i in input().split()]
if n>=24:
  print(0)
else:
  ans=0
  for i in range(2**(n-1)):
    C=[1]+[0]*23+[1]
    C[D[0]]+=1
    for j in range(n-1):
      if i&(1<<j):
        C[24-D[j+1]]+=1
      else:
        C[D[j+1]]+=1
    cur=24
    if max(C)==1:
      t=0
      for j in range(1,25):
        if C[j]:
          cur=min(cur,t+1)
          t=0
          if not cur:
            break
        else:
          t+=1
    else:
      cur=0
    ans=max(ans,cur)
  print(ans)





### FIXED CODE ###

n=int(input())
D=[int(i) for i in input().split()]
C=[1]+[0]*12

for d in D:
  C[min(d,24-d)]+=1
if max(C)>2 or C[0]>1 or C[12]>1:
  print(0)
else:
  ans=0
  
  for i in range(2**(11)):
    CC=[1]+[0]*23+[1]
    for j in range(1,12):
      if C[j]==2:
        CC[j]=1
        CC[24-j]=1
      elif C[j]==1:
        if i&(1<<(j-1)):
          CC[j]=1
        else:
          CC[24-j]=1
    if C[12]==1:
      CC[12]=1
    cur=24
    t=0
    for j in range(1,25):
      if CC[j]==1:
        cur=min(cur,t+1)
        t=0
      else:
        t+=1
    ans=max(ans,cur)
  print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())

targets = []
n_target_h = [0] * H
n_target_w = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    targets.append((h, w))
    n_target_h[h - 1] += 1
    n_target_w[w - 1] += 1

h_max = max(n_target_h)
w_max = max(n_target_w)

bomb_h = [i + 1 for i, h in enumerate(n_target_h) if h == h_max]
bomb_w = [i + 1 for i, w in enumerate(n_target_w) if w == w_max]

ans = 0
for h in bomb_h:
    for w in bomb_w:
        if (h, w) in targets:
            ans = max(h_max + w_max - 1, ans)
        else:
            ans = h_max + w_max

print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())

targets = []
n_target_h = [0] * H
n_target_w = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    targets.append((h, w))
    n_target_h[h - 1] += 1
    n_target_w[w - 1] += 1

h_max = max(n_target_h)
w_max = max(n_target_w)

bomb_h = [i + 1 for i, h in enumerate(n_target_h) if h == h_max]
bomb_w = [i + 1 for i, w in enumerate(n_target_w) if w == w_max]

count = len(bomb_h) * len(bomb_w)
for target in targets:
    if (n_target_h[target[0] - 1] == h_max) and (n_target_w[target[1] - 1] == w_max):
        count -= 1

if count > 0:
    ans = h_max + w_max
else:
    ans = h_max + w_max - 1

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

K, S = [int(i) for i in input().split()]
cnt = 0 
x_flg = bool()
out = int()
for x in range(0,K+1):
  for y in range(0,K+1):
    if 0 <= S - x < K:
      cnt += S - x + 1
      break
    z = S - (x + y)
    if K >= x and K >= y and K >= z and z >= 0:
      cnt += 1
    elif z < 0:
      break
print(cnt)

### FIXED CODE ###

K, S = [int(i) for i in input().split()]
cnt = 0 
for x in range(0,K+1):
  if 0 <= S - x <= K:
    cnt += S - x + 1
  elif 0 <= S - x <= 2*K:
    cnt += 2*K - S + x + 1
print(cnt)
### BUGGY CODE ###

N = int(input())
pwr = 1
for i in range(1, N+1):
    pwr = pwr * i
print(pwr % (10**9+7))

### FIXED CODE ###

import math
N = int(input())
print(math.factorial(N) % (10**9+7) )
### BUGGY CODE ###

from math import floor

A,B,N = map(int,input().split())
Max = -100000000000000
for i in range(1,N+1):
    Max = max(Max,floor(A*i/B)-A*floor(i/B))

print(Max)

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(N,B-1)
print(int(A*x/B))