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

import copy
H, W = map(int, input().split())
MAP = [list('#' + input() + '#') for j in range(H)]
MAP.insert(0, ['#' for i in range(W + 2)])
MAP.append(['#' for i in range(W + 2)])
MAP2 = copy.deepcopy(MAP)


def line(MAP):
    for i in range(1, H + 2):
        before = 0
        for j in range(1, W + 2):
            if MAP[i][j] == '#':
                for x in range(before + 1, j):
                    MAP[i][x] = j - before - 1
                before = j


def column(MAP2):
    for j in range(1, W + 2):
        before = 0
        for i in range(1, H + 2):
            if MAP2[i][j] == '#':
                for y in range(before + 1, i):
                    global ans
                    ans = max(ans, i - before - 1 + MAP[y][j])
                before = i


line(MAP)
ans = 0
column(MAP2)
print(ans - 1)

### FIXED CODE ###

def main ():
    H, W = map(int, input().split())
    MAP = [list('#' for i in range(W + 2)) for j in range(H + 2)]
    for i in range(H):
        line = list(input())
        for j, dot in enumerate(line):
            MAP[i + 1][j + 1] = dot
    L = [[0 for j in range(W + 2)] for i in range(H + 2)]


    def line(MAP):
        for i in range(1, H + 2):
            before = 0
            for j in range(1, W + 2):
                if MAP[i][j] == '#':
                    for x in range(before + 1, j):
                        L[i][x] = j - before - 1
                    before = j


    def column(MAP2):
        ans = 0
        for j in range(1, W + 2):
            before = 0
            for i in range(1, H + 2):
                if MAP2[i][j] == '#':
                    for y in range(before + 1, i):
                        ans = max(ans, i - before - 1 + L[y][j])
                    before = i
        return ans - 1

    line(MAP)
    column(MAP)
    print(column(MAP))

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

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
	ans.append(a[i])
	ans.reverse()
ans_s ='' 
for j in range(n):
	ans_s += str(ans[j])
	ans_s += ' '
print(ans_s)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
head_s = [] 
back_s = []
n2 = 1
if n%2 == 0:
	n2 = 0
for h in range(n-1,-1,-2):
	head_s.append(a[h])
for b in range(n2,n,2):
	back_s.append(a[b])
#print(head_s,back_s)
ans_h = (' '.join(map(str,head_s)))
ans_b = (' '.join(map(str,back_s)))
print(ans_h,ans_b)
### BUGGY CODE ###

MOD = 1000000007

def modpow(ori, po):
	res = 1;
	while(po > 0):
		if(po&1):
			res *= ori;
			res %= 13;
		ori *= ori;
		ori %= 13;
		po >>= 1;
	return res;


S = input()
memo = [[0] * 13 for i in range(len(S)+1)]

memo[0][0] = 1
for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			mod = (modpow(10, (len(S) - idx - 1)) * num)%13
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i+mod)%13] += memo[idx][i] 
					memo[idx+1][(i+mod)%13] %= MOD
	else:
		num = int(ch)
		mod = (modpow(10, (len(S) - idx - 1)) * num)%13
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i+mod)%13] += memo[idx][i] 
				memo[idx+1][(i+mod)%13] %= MOD

print(memo[len(S)][5]%MOD)

### FIXED CODE ###

MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	else:
		num = int(ch)
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)
### BUGGY CODE ###

n = int(input())
a = n** 0.5
if n%a == 0:
    print(int(2*a)-2)
else:
    while n%a != 0:
        a = a//1+1 
        if n%a == 0:
            print(int(a + n//a-2))
            exit()

### FIXED CODE ###

n = int(input())
#a,b = map(int,input().split())
#li = list(map(int,input().split()))
li = []
for i in range(1,int(n**0.5//1)+1):
    if n%i == 0:
        li.append(i+n//i-2)
        #print(i,n//i)
if len(li)!=0:
    print(min(li))
else:
    print(n-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)
        

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###

# coding: utf-8
import sys,pprint
from fractions import Fraction
from collections import defaultdict

N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(int)
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
    elif bi == 0:
        zerodiv += 1
    else:
        t = Fraction(ai,bi)
        tilts[t] += 1

print(tilts,file=sys.stderr)

ans = 1
f1 = Fraction(0,1)
if f1 in tilts:
    ans *= 1+pow(2,tilts[f1])-1 + pow(2,zerodiv)-1
    del tilts[f1]
else:
    ans *= 1 + pow(2,zerodiv)-1

klist = list(tilts.keys())
for k in klist:
    kinv = Fraction(-1*k.denominator,k.numerator)
    if kinv in tilts:
        #print(k,kinv, file=sys.stderr)
        ans *= 1+pow(2,tilts[k]) -1+pow(2,tilts[kinv])-1
        del tilts[k]
        del tilts[kinv]
    else:
        ans *= 1+pow(2,tilts[k])-1

print((ans + zerozero -1)%1000000007)


### FIXED CODE ###

# coding: utf-8
import sys,pprint, math
from fractions import Fraction
from collections import defaultdict

MOD = 1000000007
N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(lambda: [0,0])
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
        continue
    if (ai < 0) or (ai == 0 and bi < 0):
        ai *= -1
        bi *= -1
    g = math.gcd(ai,bi)
    ai = ai // g
    bi = bi // g
    if bi > 0:
        tilts[(ai,bi)][0] += 1
    else:
        tilts[(-bi,ai)][1] += 1
print(tilts,file=sys.stderr)

#sys.exit()
ans = 1
for(v1,v2) in tilts.values():
    ans *= 1 +pow(2,v1,MOD)-1 +pow(2,v2,MOD)-1
    ans %= MOD
ans = (ans+zerozero-1) % MOD
print(ans)
### BUGGY CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,m=map(int,input().split())

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



for i in range(m):
	A=sorted(A)
	A[n-1]//=2
	
print(sum(A))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍

heapq.heapify(a)

for i in range(m):
    minimum=heapq.heappop(a)
    mini=((minimum*(-1))//2)*(-1)
    heapq.heappush(a,mini)
    
print(-sum(a))
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
  string = input().split()
  if string[0] == '1':
    S = S[::-1]
  elif string[1] == '1':
      S = string[2] + S
  else:
      S = S + string[2]
print(S)

### FIXED CODE ###

from collections import deque
S = deque()
tmp = input()
for i in range(len(tmp)):
  S.append(tmp[i])
Q = int(input())
flag = True
for i in range(Q):
  string = input().split()
  if string[0] == '1':
    flag = not flag
  elif flag ^ (string[1] == '1'):
      S.append(string[2])
  else:
      S.appendleft(string[2])
if not flag:
  S.reverse()
for s in S:
  print(s, end='')
### BUGGY CODE ###

S = input()
K = int(input())
N = len(S)

s = sorted(S)
s = s[0:4]

L = []
for i in range(N):
    if S[i] in s:
        for j in range(i+1,N+1):
            a = S[i:j]
            if a not in L:
                L.append(a)
L.sort()
print(L[K-1])

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)

l = []
for i in range(N):
    for j in range(i+1,min(i+K+1,N+1)):
        s = S[i:j]
        l.append(s)
l = list(set(l))
l.sort()
print(l[K-1])
### BUGGY CODE ###

N = int(input())
A = list(map(lambda x: format(int(x), "060b"), input().split()))
Num = 10**9 + 7
digit = [0 for i in range(60)]
for a in A:
  for i in range(60):
    if a[i] == "1":
      digit[i] += 1
#print(digit)
ans = 0
for i in range(60):
  ans = (ans * 2 + digit[i] * (N-digit[i])) %Num
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(lambda x: format(int(x), "060b"), input().split()))
Num = 10**9 + 7
digit = [0 for i in range(60)]
for a in A:
  for i in range(60):
    if a[i] == "1":
      digit[i] += 1
#print(digit)
ans = 0
for i in range(60):
  ans = (ans * 2 + digit[i] * (N-digit[i])) %Num
print(ans)
### BUGGY CODE ###

import sys
from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, MOD) - comb(m, i-1, MOD)
        print(int(ans) % MOD)


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

import numpy as np

A = [int(x) for x in input().split(' ')]
N = A[0]
M = A[1]
PY = []
for i in range(M):
    PY.append(input().split(' '))

PY = np.array(PY).astype(int)
P = [int(PY[i][0]) for i in range(M)]
#Y = [int(PY[i][1]) for i in range(M)]
P_list = set(P)

for x in P_list:
    Y = set(PY[(PY[:,0]==x),1])
    Y = sorted(Y)
    for i in range(len(Y)):
        PY[(PY[:,1]==Y[i]),1] = i+1

for i in range(M):
    print('%06d'%PY[i][0], end='')
    print('%06d'%PY[i][1])

### FIXED CODE ###

N, M = map(int, input().split())
D = [[] for i in range(N)]

for i in range(M):
    P, Y = map(int, input().split())
    D[P-1].append((Y,i))

ans = [None] * M

for i, d in enumerate(D):
    d.sort()
    for k, (y, j) in enumerate(d):
        ans[j] = str(i+1).zfill(6) + str(k+1).zfill(6)
print(*ans, sep='\n')
### BUGGY CODE ###

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

for i in range(n):
  a[i] -= i + 1

average = sum(a) // n

#print(average)

def sadness(a, ave):
  sad = 0
  for i in range(n):
    sad += abs(a[i] - ave)
  return sad

result = sadness(a, average)

temp = average
for i in range(1, n):
  temp_result = sadness(a, average + i)
  if result < temp_result:
    break
  else:
     temp = average + i
     result = temp_result

for i in range(1, n):
  temp_result = sadness(a, average - i)
  if result < temp_result:
    break
  else:
     temp = average - i
     result = temp_result

print(result)

### FIXED CODE ###

from statistics import median

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

for i in range(n):
  a[i] -= i + 1

ave = int(median(a))

sad = 0
for i in range(n):
  sad += abs(a[i] - ave)

print(sad)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)
sa = sum(A) 
l = -1 
r = A[N-1] * F[0]
while l+1 < r: 
    m = (l + r) //2
    S = sa
    for i in range(N):
        S -= min(m // F[i], A[i])
    if S <= K:
        r = m
    else:
        l = m
         
print(r)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)
sa = sum(A) 
A = np.array(A)
F = np.array(F)

l = -1 
r = A[N-1] * F[0]
while l+1 < r: 
    m = (l + r) //2
    S = sa - np.sum(np.minimum(m // F, A)) 
    if S <= K:
        r = m
    else:
        l = m
         
print(r)
### BUGGY CODE ###

import math
from collections import Counter

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

cnt = Counter(a)
a = list(set(a))
a.sort()

def eratosthenes(a):
    cand = a
    ans = 0
    while cand:
        p = cand[0]
        if cnt[p] == 1:
            ans += 1
        nex = []
        for num in cand:
            if num == p:
                continue
            if num % p:
                nex.append(num)
        cand = nex
    return ans

print(eratosthenes(a))

### FIXED CODE ###

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

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

from itertools import product
n, k = map(int, input().split())
dots = [list(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for a, b, c, d in product(dots, repeat=4):
	upper = max(a[1], b[1], c[1], d[1])
	lower = min(a[1], b[1], c[1], d[1])
	left = min(a[0], b[0], c[0], d[0])
	right = max(a[0], b[0], c[0], d[0])

	area = (upper - lower) * (right - left)
	num = 0
	for dot in dots:
		if left <= dot[0] <= right and lower <= dot[1] <= upper:
			num += 1
	if num >= k and area < ans:
		ans = area

print(ans)

### FIXED CODE ###

from itertools import combinations
n, k = map(int, input().split())
dots = sorted([list(map(int, input().split())) for _ in range(n)])

ans = float("inf")
for x1, x2 in combinations(range(n), 2):
	wid = dots[x2][0] - dots[x1][0]
	dots_cand = sorted(dots[x1: x2 + 1], key=lambda x: x[1])
	for y1, y2 in combinations(range(x2 + 1 - x1), 2):
		if y2 - y1 + 1 >= k:
			area = (dots_cand[y2][1] - dots_cand[y1][1]) * wid
			if area < ans:
				ans = area

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

X, K, D = [int(x) for x in input().split()]

s=X

for i in range(K):
    if abs(s - D) < abs(s + D):
        s -= D
    else:
        s += D
print(abs(s))

### FIXED CODE ###

X, K, D = [int(x) for x in input().split()]

X=abs(X)
s = min(K, X//D)
K = K - s
X = X - s*D
#print(s, K, X)
if K%2 == 0:
    print(X)
else:
    print(D-X)
### BUGGY CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * nowQues  # (3 ** ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * (nowQues//3)  # (3 ** (ques - 1))
            ques += 1
            nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * nowQues  # (3 ** ques)
            if ques > 0:
                ab += ques * (nowQues//3)  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu


print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))


### FIXED CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))
### BUGGY CODE ###

import heapq
import math


def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[float('inf')] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = 0
                q.append([-0, x, y])
    heapq.heapify(q)
    while q:
        d, x, y = heapq.heappop(q)
        dd = -d + 1
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h:
                if aa[yy][xx] == '.' and dist[yy][xx] > dd:
                    dist[yy][xx] = dd
                    heapq.heappush(q, [-dd, xx, yy])
    m = 0
    for row in dist:
        for v in row:
            if not math.isinf(v) and v > m:
                m = v
    print m


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[False] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = True
                q.append([x, y])
    m = 0
    nexts = []
    while True:
        for x, y in q:
            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                xx = x + dx
                yy = y + dy
                if 0 <= xx < w and 0 <= yy < h:
                    if aa[yy][xx] == '.' and not dist[yy][xx]:
                        dist[yy][xx] = True
                        nexts.append([xx, yy])
        if nexts:
            m += 1
            q = nexts
            nexts = []
        else:
            break
    print m


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

N, M = map(int, input().split())
nodes = [i for i in range(N)]


def root(x):
    while nodes[x] != x:
        x = nodes[x]
    return x


def same(x, y):
    return root(x) == root(y)


def unite(x, y):
    if not same(x, y):
        nodes[root(y)] = root(x)


for _ in range(M):
    X, Y, Z = map(int, input().split())
    unite(X-1, Y-1)


ans = 0
for i in range(len(nodes)):
    if nodes[i] == i:
        ans += 1

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
nodes = [i for i in range(N)]


def root(x):
    if nodes[x] == x:
        return x
    else:
        nodes[x] = root(nodes[x])
    return nodes[x]


def same(x, y):
    return root(x) == root(y)


def unite(x, y):
    if not same(x, y):
        nodes[root(x)] = root(y)


for _ in range(M):
    X, Y, Z = map(int, input().split())
    unite(X-1, Y-1)


ans = 0
for i in range(len(nodes)):
    if nodes[i] == i:
        ans += 1

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

import sys
input = sys.stdin.readline

def inv(x):
    return pow(x, MOD-2, MOD)
    
def C(n, r):
    return fact[n]//fact[r]//fact[n-r]

N = int(input())
x = list(map(int, input().split()))
ans = 0
MOD = 10**9+7
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i)
    
for i in range(N-1):
    for j in range(i+1, N):
        #print(i, j)
        
        r = j-i+1
        
        if j==N-1:
            r = N-2-i+1
            ans += (x[j]-x[i])*C(N-1, r)*fact[r-1]*fact[N-1-r]
            #print(C(N-1, r-1)*fact[N-1-r+1]*fact[r-2])
        else:
            r = j-i+1
            ans += (x[j]-x[i])*C(N-1, r)*fact[j-i-1]*fact[N-1-r]
        #print(x[j]-x[i])
            #print(C(N-1, r)*fact[N-1-r]*fact[r-2])
        #ans += (x[j]-x[i])*C(N-1, r)*fact[N-1-r]
        #print('ans:', ans)
        ans %= MOD

#ans *= fact[N-1]
ans %= MOD

print(ans)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
MOD = 10**9+7
D = x[-1]-x[0]
ans = 0
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i%MOD)

inv_table = [-1]*N

for i in range(N):
    inv_table[i] = pow(i, MOD-2, MOD)
    
for i in range(N-1):
    d = D-(x[i]-x[0])
    ans += d*fact[N-1]*inv_table[i+1]
    ans %= MOD

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

import numpy as np
from collections import defaultdict

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

    memo[(v, d)] = True
    if d == 0:
        res[v-1] = c
        return None

    dp(v, d-1, c)
    for e in dic.get(v, []):
        dp(e, d-1, c)


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

dic = defaultdict(list)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a].append(b)
    dic[b].append(a)

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


for i in range(N):
    print(int(res[i]))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))