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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(('R', r))
	VectorSet.add(('C', c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()
		
print("Yes")


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

n = int(input())
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j] and i > j:
            dp[i][j] = min(dp[i+1][j+1] + 1, i-j)
            ans = max(ans, dp[i][j])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0

for i in range(n):
    a = n-1-i
    for j in range(n):
        b = n-1-j
        if s[a] == s[b]:
            dp[a][b] = dp[a+1][b+1] + 1
for i in range(n):
    for j in range(n):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0
#L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        maxi = L[i] + L[j]
        mini = abs(L[i] - L[j]) 
        for k in range(j+1,N):
            if maxi > L[k] and L[k]> mini:
                count += 1 
print(count)


### FIXED CODE ###


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

# -*- condig:utf-8 -*-

import sys
sys.setrecursionlimit(100000000)

def dfs(p, parents, count):
  parents.append(p)
  count += o.get(p, 0)
  for i in g[p]:
    if not i in parents:
      dfs(i, parents, count)
  counter[p] = counter.get(p, 0) + count
  parents.remove(p)
 

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

g = {}
o = {}
counter = {}
for i in range(n-1):
  a,b= map(int, input().split())
  if not g.get(a, False):
    g[a] = [b]
  else:
    if not b in g[a]:
      g[a].append(b)
  if not g.get(b, False):
    g[b] = [a]
  else:
    if not a in g[b]:
      g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  if not o.get(p, False):
    o[p] = x
  else:
    o[p] = o[p] + x

dfs(1, [], 0)
for i in range(1, n+1):
  print(counter.get(i, 0), end=' ')

 
  


### FIXED CODE ###


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

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
  p = todo.pop(-1)
  ct[p] += o[p]
  seen[p] = True
  for i in g[p]:
    if seen[i]:
      ct[p] += ct[i]
    else:
      todo.append(i)

print(*ct[1:])
### BUGGY CODE ###

import itertools
N = int(input())
L = list( map( int, input().split() ) )
comb = []
for n in itertools.combinations(L, 3):
  if (n[0] + n[1] > n[2]) and (n[1] + n[2] > n[0]) and (n[2] + n[0] > n[1]):
        comb.append( ' '.join( str(x) for x in sorted(n) ) )
print( len( set(comb) ) )

### FIXED CODE ###

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

import bisect
L=sorted(L)
comb = 0
for a in range(N-2):
    for b in range(1+a,N-1):
        posIndex = bisect.bisect_left(L, L[a] + L[b])
        comb += posIndex - b - 1 if posIndex != 0 else 0
print(comb)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from bisect import insort

x,y,a,b,c=nii()
p=lnii()
q=lnii()
r=lnii()

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

l=p[:x]+q[:y]
l.sort()

for i in r:
  insort(l,i)

l.sort(reverse=True)
print(sum(l[:x+y]))

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())),reverse=True)
q=sorted(list(map(int,input().split())),reverse=True)
r=sorted(list(map(int,input().split())),reverse=True)

list=p[:x]+q[:y]

if len(list)<x+y:
  ll=len(list)
  for i in range((x+y)-len(list)):
    list.append(r[i])
  r=r[(x+y)-ll:]
list=sorted(list)

for i in range(len(r)):
  if list[i]<r[i]:
    list[i]=r[i]
  else:
    break
print(sum(list))
### BUGGY CODE ###

import numpy as np

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

A_ = sorted(A_)
A = np.array(A_)

ans = 0
for X in A:
    tmp = 0
    tmp = np.sum((X-1 <= A) & (A<= X+1))
    ans = max(tmp,ans)
# dic = {}
# for a in A:
#     dic[a] = 0

# for a in A:
#     dic[a] += 1


# ans = max(ans,dic[X] + dic[X+1])

# for X in A[1:]:

#     tmp = dic[]


#     tmp = dic[dic.key()] + dic[X] + dic[X+1]

#     ans = max(tmp,ans)
print(ans)


### FIXED CODE ###

import collections

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

dic = collections.Counter(A)
tmp = [0 for _ in range(A[-1]+1)]


for X in dic.keys():
    tmp[X] = dic[X]

ans = 0
for i in range(len(tmp)):
    ans = max(ans,sum(tmp[i:i+3]))

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

S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    newdp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                newdp[(p + j) % 13] += dp[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            newdp[(p + j) % 13] += dp[j]%(10**9+7)
    dp=newdp
    i += 1


print(dp[5]%(10**9+7))

### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
### BUGGY CODE ###

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

while len(A) > 1:
    m = A[0]
    for n in range(1, len(A)):
        A[n] = A[n] % m
    A = list(set(A))
    if A[0] == 0:
        A = A[1:]
print(A[0])

### FIXED CODE ###

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

while num > 1:
    a = min(A)
    j = 0
    flag = True
    for n in range(num):
        if A[n] == a and flag:
            A[j] = a
            j += 1
            flag = False
        else:
            b = A[n] % a
            if b > 0:
                A[j] = b
                j += 1
    num = j

print(A[0])
### BUGGY CODE ###

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

from collections import Counter
from collections import defaultdict
from collections import deque 
def main():
    N, X, Y = map(int, readline().split())
    to = [[] for _ in range(N)] 

    for i in range(N-1):
        to[i].append(i+1)
        to[i+1].append(i)
    to[X-1].append(Y-1)
    to[Y-1].append(X-1)
    INF = int(1e9)
    ans = defaultdict(int)
    for si in range(N):
        dq = deque()
        dq.append(si)
        dist = [INF for _ in range(N)]
        dist[si] = 0
        while len(dq)>0:
            v = dq.popleft()
            for nx in to[v]:
                if dist[nx] != INF:
                    continue
                dq.append(nx)
                dist[nx] = dist[v]+1
        for i in dist:
            ans[i] += 1
    
    for i in range(1, N):
        print(ans[i]//2)
if __name__ == '__main__':
    main()


### FIXED CODE ###


from collections import deque
from collections import Counter
from collections import defaultdict
INF = int(1e9)
def main():
    n, x, y = map(int, input().split())
    x-=1
    y-=1
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[i].append(i+1)
        g[i+1].append(i)
    g[x].append(y)
    g[y].append(x)
    ans = defaultdict(int)
    q = deque()
    pns = []
    for i in range(n):
        dist = [INF for _ in range(n)]
        q.append(i)
        dist[i] = 0
        while len(q):
            node_s = q.popleft() 
            for j in range(len(g[node_s])):
                if dist[g[node_s][j]] != INF:
                    continue
                q.append(g[node_s][j])
                dist[g[node_s][j]] = dist[node_s] + 1
        for k in range(n): 
            pns.append(dist[k])
    
    ans = Counter(pns) 
    for k in range(1, n):
        print(ans[k]//2)
main()
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    s=input()
    if s not in a:
        a.append(s)

print(len(a))

### FIXED CODE ###

n=int(input())
a=[0]*n

for i in range(n):
    a[i]=input()
a=sorted(a)
ans=1
for i in range(n-1):
    if a[i]!=a[i+1]:
        ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n):
    ans.append(a.index(i+1)+1)
print(*ans)

### FIXED CODE ###

n=int(input())
num=[i+1 for i in range(n)]
L=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for j in range(n):
    ans[L[j]-1]=num[j]
print(*ans)
### BUGGY CODE ###

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

def isPrime(n):
  if n < 2:
    return False
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i += 1
  return True

def Eratosthenes(n):

    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    for i in range(2,n):
        if dp[i]:
            continue
        prime.append(i)
        for j in range(i*2,n,i):
          dp[j] = True
    return prime

cnt = 0
for i in range(Q):
  E = Eratosthenes(LR[i][1]+1)
  #print(E)
  for j in E:
    if j >= LR[i][0] and isPrime(j) and isPrime((j + 1)//2):
      cnt += 1
  print(cnt)
  cnt = 0

### FIXED CODE ###

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
flg = [False] * (10**5+1)

def isPrime(n):
  if n < 2:
    return False
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i += 1
  return True

def Eratosthenes(n):
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    for i in range(2,n):
        if dp[i]:
            continue
        prime.append(i)
        for j in range(i*2,n,i):
          dp[j] = True
    return prime

Era = Eratosthenes(10**5+1)
for e in Era:
  flg[e] = True

cnt = []
tmp = 0
for i in range(10**5+1):
  if flg[i] and flg[(i+1)//2]:
    tmp += 1
  cnt.append(tmp)

for i in range(Q):
  print(cnt[LR[i][1]] - cnt[LR[i][0]-1])
### BUGGY CODE ###

n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W[i]):
        DP[i+1][j] = DP[i][j]
    for j in range(W[i], m+1):
        DP[i+1][j] = max(DP[i][j], DP[i][j-W[i]]+V[i])
print(DP[n][m])


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [[0 for m in range(M + 1)] for n in range(N + 1)]
for n in range(N):
    for m in range(M + 1):
        if m < W[n]:
            f[n + 1][m] = f[n][m]
        else:
            f[n + 1][m] = max(f[n][m], f[n][m - W[n]] + V[n])
print(f[N][M])
### BUGGY CODE ###

N=int(input())
list1=list(map(int,input().split()))
#print(list1)

ans_list=[]
ans=0
for i in range(N):
	j=i
	ans=0
	while True:
		if j==N-1:
			break
		if list1[j]>=list1[j+1]:
			ans+=1
			j+=1
		else :
			break

	ans_list.append(ans)
print(max(ans_list))

### FIXED CODE ###

N=int(input())
list1=list(map(int,input().split()))
#print(list1)
ans_list=[]
j=0
while True:
	ans=0
	while True:
		if j==N-1:
			break
		if list1[j]>=list1[j+1]:
			ans+=1
			j+=1
		else :
			break
	j+=1
	ans_list.append(ans)
	if j==N:
		break
print(max(ans_list))
### BUGGY CODE ###

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

for i in range(n):
    ans *= a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    print(0)
    exit()

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

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

N,K=map(int,input().split())
p=list(map(int,input().split()))
def P(x):
    return (x+1)/2
a=0
for i in range(N-K+1):
    y=0#隣接区間の期待値の和
    for j in range(K):
        y+=P(p[i+j])
    if a<y:
        a=y
print(a)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
def P(x):
    return (x+1)/2
a=0
y=0
for i in range(N):
    y+=P(p[i])#区間内の期待値の和
    if i>=K:
        y-=P(p[i-K])
    if a<y:
        a=y
print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
mod = 10**9+7
setA = []
for i in range(N):
  if A[-1]%A[i] != 0 or i == N-1:
    setA.append(A[i])

import fractions
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
 
l = lcm(*setA)
B = 0
for i in range(N):
  B += l//A[i]%mod
B %= mod
print(B)

### FIXED CODE ###

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

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
for i in range(Q):
    l, r = map(int, input().split())
    cnt = int()
    tmp = S[l-1:r]
    # print(tmp)
    for j in range(r-l):
        if tmp[j:j+2] == 'AC':
            cnt += 1

    print(cnt)


### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
L = [0]  # ruisekiwa
for i in range(1, len(S)):
    if S[i-1:i+1] == 'AC':
        L.append(L[i-1]+1)
    else:
        L.append(L[i-1])

for i in range(Q):
    l, r = map(int, input().split())
    print(L[r-1]-L[l-1])
### BUGGY CODE ###

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

    b = [[0] * 60]

    for i, x in enumerate(a):
        t = list(b[-1])
        for j in range(60):
            if (x >> j) & 1:
                t[j] += 1
        b.append(t)

    ret = 0
    for i, x in enumerate(a, 1):
        for j in range(60):
            j_on = (b[-1][j] - b[i][j])
            if (x >> j) & 1:
                ret += (1 << j) * ((n - i) - j_on)
            else:
                ret += (1 << j) * j_on
            ret %= mod
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    input = sys.stdin.readline

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

    b = [0] * 60

    for j in range(60):
        for x in a:
            if (x >> j) & 1:
                b[j] += 1

    ret = 0
    for j in range(60):
        ret = (ret + b[j] * (n - b[j]) * (1 << j)) % mod

    print(ret)


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

def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    dp = [INF] * (10 ** 7)
    dp[0] = 0

    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 1):
            if dp[i] == INF:
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
    return min(dp[N:])

print(solve())

### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())
### BUGGY CODE ###

S = input()
Q = int(input())
ARR = []
for i in range(Q):
    ARR.append(input().split(" "))

def calculate(s,q,arr):
    s = list(s)
    for ar in arr:
        if int(ar[0]) == 1:
            s = list(reversed(s))

        if int(ar[0]) == 2:
            if int(ar[1]) == 1:
                s.insert(0,ar[2])
            else:
                s.append(ar[2])

    print("".join(s))



calculate(S,Q,ARR)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
ARR = []

for i in range(Q):
    arr = input().split(" ")
    ARR.append(arr)


def calculate(s,q,arr):
    s = deque(list(s))

    kk = 0
    for ar in arr:
        if int(ar[0]) == 1:
            kk = kk + 1
        if int(ar[0]) == 2:
            if int(ar[1]) == 1:
                if kk % 2 == 0:
                    s.appendleft(ar[2])
                else:
                    s.append(ar[2])
            else:
                if kk % 2 == 0:
                    s.append(ar[2])
                else:
                    s.appendleft(ar[2])

    if kk % 2 == 1:
        s.reverse()

    print("".join(list(s)))

calculate(S,Q,ARR)
### BUGGY CODE ###

import math

MOD = 10**9 + 7


def pathes(x, y):
    return math.factorial(x + y) // (math.factorial(x) * math.factorial(y))


def main():
    r1, c1, r2, c2 = map(int, input().split())

    a = pathes(r1, c1) - 1
    b = pathes(r1, c2 + 1) - 1
    c = pathes(r2 + 1, c1) - 1
    d = pathes(r2 + 1, c2 + 1) - 1

    print((d - c - b + a) % MOD)


main()


### FIXED CODE ###

import fractions
from functools import reduce
import math

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


# def pathes(x, y):
#     xf = None
#     yf = None
#     xyf = None
#     temp = 1
#     for i in range(1, x + y + 1):
#         temp *= i % MOD
#         if i == x:
#             xf = temp
#         if i == y:
#             yf = temp
#         if i == x + y:
#             xyf = temp
#     # xf = math.factorial(x) % MOD
#     # yf = math.factorial(y) % MOD
#     # xyf = math.factorial(x + y) % MOD

#     return xyf * modinv(xf * yf % MOD, MOD)


def pathes(rf, cf, rcf):
    return rcf * modinv((rf * cf) % MOD, MOD)


def main():
    r1, c1, r2, c2 = map(int, input().split())

    f = [1 for _ in range(r2 + c2 + 2 + 1 + 1)]

    for i in range(1, r2 + c2 + 2 + 1):
        f[i] = f[i - 1] * i % MOD

    a = (pathes(f[r1], f[c1], f[r1 + c1]) - 1) % MOD
    b = (pathes(f[r1], f[c2 + 1], f[r1 + c2 + 1]) - 1) % MOD
    c = (pathes(f[r2 + 1], f[c1], f[r2 + 1 + c1]) - 1) % MOD
    d = (pathes(f[r2 + 1], f[c2 + 1], f[r2 + c2 + 2]) - 1) % MOD

    print((d - c - b + a) % MOD)


main()
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
sum = 0

for i in range(K):
    for j in range(K):
        for k in range(K):
            sum += gcd((i+1),(j+1),(k+1))

print(sum)



### FIXED CODE ###

from math import gcd

K = int(input())
sum = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(gcd(i,j),k)

print(sum)
### BUGGY CODE ###

def main():
    from collections import deque
    import sys

    n,m =map(int,input().split())
    abl=[[] for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a-1].append(b)
        abl[b-1].append(a)

    an=[0]*(n-1)
    tg = deque([1])
    wwk =deque([])
    while not(all(an)):
        while len(tg):
            itg = tg.pop()
            for j in abl[itg-1]:
                if an[j-2]==0 and j!=1:
                    an[j-2]=itg
                    wwk.append(j)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    if all(an):
        print('Yes')
        for j in an:
            print(j)
    else:
        print('No')

main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
for _ in range(Q):
  l, r = map(int, input().split())
  s = S[l-1:r]
  print(s.count('AC'))

### FIXED CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
### BUGGY CODE ###

import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array(sorted([LI() for _ in range(N)]))
sum_norm = 0
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        sum_norm += np.linalg.norm(xy[a[i+1]]-xy[a[i]])
print(sum_norm/math.factorial(N))


### FIXED CODE ###

import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array([LI() for _ in range(N)])
sum_norm = 0
dict_norm = {}
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        vector = xy[a[i+1]]-xy[a[i]]
        if not tuple(vector) in dict_norm:
            dict_norm[tuple(vector)] = np.linalg.norm(vector)
        sum_norm += dict_norm[tuple(vector)]
print(sum_norm/math.factorial(N))