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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    q = int(readline())
    mat = [[] for _ in range(q)]

    for i in range(q):
        mat[i] = list(map(int, readline().split()))

    paint = [[0, -1] for _ in range(n + 1)]
    outer = defaultdict(list)

    for v, d, c in mat[::-1]:
        if d == 0 and paint[v] == -1:
            paint[v][0] = c
            paint[v][1] = 0
        else:
            if paint[v][1] >= d:
                continue
            que = deque()
            que.append((v, d, c))
            visited = [False] * (n+1)
            while que:
                cur, rem, color = que.popleft()
                visited[cur] = True
                if paint[cur][0] == 0:
                    paint[cur][0] = color
                    paint[cur][1] = rem
                    outer[v].append(cur)
                if rem > 0:
                    n_rem = rem - 1
                    for nx in edge[cur]:
                        if visited[nx]:
                            continue
                        if paint[nx][1] >= n_rem:
                            pass
                        else:
                            que.append((nx, n_rem, color))

    for i in range(1, n + 1):
        print(paint[i][0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    q = int(readline())
    mat = [[] for _ in range(q)]

    for i in range(q):
        mat[i] = list(map(int, readline().split()))

    dp = [[0] * 11 for _ in range(n + 1)]

    for v, d, c in mat[::-1]:
        if dp[v][d] != 0:
            continue
        que = deque()
        que.append((v, d, c))
        while que:
            cur, dist, color = que.popleft()
            for i in range(dist, -1, -1):
                if dp[cur][i] == 0:
                    dp[cur][i] = color
                else:
                    break
            if dist > 0:
                for nx in edge[cur]:
                    if dp[nx][dist - 1] != 0:
                        continue
                    else:
                        que.append((nx, dist - 1, color))

    for i in range(1, n + 1):
        print(dp[i][0])


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

n=int(input())
a=list(input().split())
b=[]

for i in range(n):
  b.append(a[i])
  b.reverse()
print(" ".join(b))

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(input().split())
b=deque()

for i in range(1,n+1):
  if (i%2==1 and n%2==0) or (i%2==0 and n%2==1):
    b.append(a[i-1])
  else:
    b.appendleft(a[i-1])
print(" ".join(b))
### BUGGY CODE ###

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

nA = [line[:] for line in A]
cnt = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if nA[i][j] > nA[i][k] + nA[k][j]:
                nA[i][j] = nA[i][k] + nA[k][j]
            elif not(i == j or j == k or k == i) and nA[i][j] == nA[i][k] + nA[k][j]:
                cnt += nA[i][j]

if A != nA:
    print(-1)
else:
    ans = sum(sum(line) for line in A) - cnt
    ans //= 2
    print(ans)

### FIXED CODE ###

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

flag = [[0] * N for _ in range(N)]
dist = [line[:] for line in A]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or j == k or k == i:
                continue
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
            elif dist[i][j] < dist[i][k] + dist[k][j]:
                flag[i][j] += 1

if A != dist:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] == N-2:
            ans += A[i][j]

ans //= 2
print(ans)
### BUGGY CODE ###

N=int(input())
S=list(str(input()))
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)
ans=len(G)*len(B)*len(R)
for r in R:
	for g in G:
		if (2*g-r) in B:
			ans-=1
		if (2*r-g) in B:
			ans-=1
		if (g+r)/2 in B:
			ans-=1
print(ans)



### FIXED CODE ###

N=int(input())
S=list(str(input()))
R=0
G=0
B=0
for i in range(N):
	if S[i]=='R':
		R+=1
	elif S[i]=='G':
		G+=1
	else:
		B+=1
ans=G*B*R
for a in range(N-1):
	for d in range(1,(N-a-1)//2+1):
		if S[a]!=S[a+d] and S[a+d]!=S[a+d*2] and S[a]!=S[a+d*2]:
			ans-=1
print(ans)
### BUGGY CODE ###

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

ans = 0
for c in C:
    for b in B:
        for a in A:
            if c > b & b > a:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    a=bisect.bisect_left(A,b)
    c=bisect.bisect_right(C,b)
    ans += a *(N-c)
print(ans)
### BUGGY CODE ###

import sys

next(sys.stdin)
n = list(map(int, next(sys.stdin).split()))

while True:
    k = min(range(len(n)), key=lambda k: n[k])
    n = n[k:] + n[:k]
    for k in range(1, len(n) + 1):
        if k <= n[k - 1]:
            n[k - 1] -= k
        else:
            print('NO')
            exit()
    if sum(n) == 0:
        print('YES')
        exit()


### FIXED CODE ###

import numpy as np
import sys

n = int(next(sys.stdin))
a = np.array(list(map(int, next(sys.stdin).split())))
j = np.arange(n) + 1

if np.any(a.sum() % j.sum() > 0):
    print('NO')
    exit()

s = a.sum() // j.sum()
k = s - (a[1:] - a[:-1])
if np.all(k >= 0) and np.all(k % n == 0):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"
f=False
for i in range(m):
		a,b=map(int,input().split(" "))
		if a==1:l.append(b)
		if b==n:bone.append(a)
for i in l:
	for j in bone:
		if i == j:
			ans="POSSIBLE"
print(ans)


### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

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

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

def dfs(now,pre):
    available_color = 0  # 子ノードに使用可能な色の数
    if pre == -1:
        available_color = k-1
    else:
        available_color = k-2
    if k < len(graph[now]):
        return 0
    res = 1
    for son in graph[now]:
        if son == pre:continue
        res *= available_color
        available_color -= 1
        res %= MOD
    for son in graph[now]:
        if son == pre:continue
        res *= dfs(son,pre)
        res %= MOD

    return res

ans = (k*dfs(0,-1)) % MOD
print(ans)

### FIXED CODE ###

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

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

def dfs(now,pre):
    available_color = 0  # 子ノードに使用可能な色の数
    if pre == -1:
        available_color = k-1
    else:
        available_color = k-2
    if k < len(graph[now]):
        return 0
    res = 1
    for son in graph[now]:
        if son == pre:continue
        res *= available_color
        available_color -= 1
        res %= MOD
    for son in graph[now]:
        if son == pre:continue
        res *= dfs(son,now)
        res %= MOD

    return res

ans = (k*dfs(0,-1)) % MOD
print(ans)
### BUGGY CODE ###

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

for i in reversed(range(1,M//N+2)):
    if M%i == 0 and M//i >= N:
        print(i)
        break

### FIXED CODE ###

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

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
i = 1

while a:
    # print(a)
    for _ in range(len(a)):
        # print(i, a, cnt, a[0] != i)
        if a[0] != i:
            cnt += 1
            a.pop(0)
        else:
            a.pop(0)
            i += 1
            break
if cnt == n:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
num = 1
for i in range(n):
    if a[i] == num:
        num += 1

if num == 1:
    print(-1)
else:
    print(n-num+1)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((a, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
  if d>b:
    X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
    X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
    X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
  if c>a:
    for j in range(b,d+1):
      if i>a:
        X1[i][j-1]=((X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      else:
        X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      if j>=2:
        X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
if a==c:
  print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)
else:
  print((X1[c-1][d-1]+X2[c-1][d-1])%998244353)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
X0=[[0]*d for i in range(c)]
X1=[[0]*d for i in range(c)]
X2=[[0]*d for i in range(c)]
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=amari(X0[a-1][j-1]*(a-1))
 X1[a-1][j]=amari(X0[a-1][j-1]+X1[a-1][j-1]*(a-1))
 X2[a-1][j]=amari(X1[a-1][j-1]+X2[a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=amari((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j)
  if j>=2:
   X2[i][j-1]=amari(X1[i][j-2]+X2[i][j-2] *(i+1))
print(amari(X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1]))
### BUGGY CODE ###

import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = Is()
mat = [[0]*W for i in range(H)]
inp = []
for i in range(H):
    inp.append(list(S()))
for i in range(H):
    t = 0
    for j in range(W):
        if inp[i][j] == ".":
            t += 1
            if j == W-1:
                for k in range(j+1-t,j+1):
                    mat[i][k] += t
        elif inp[i][j] == "#":
            for k in range(j-t,j):
                mat[i][k] += t
            t = 0
#print(*mat)
for j in range(W):
    t = 0
    for i in range(H):
        if inp[i][j] == ".":
            t += 1
            if i == H-1:
                for k in range(i+1-t,i+1):
                    mat[k][j] += t
        elif inp[i][j] == "#":
            for k in range(i-t,i):
                mat[k][j] += t
            t = 0    
#print(*mat)
ans = 0
for e in mat:
    ans = max(ans,max(e))
print(max(0,ans-1))

### FIXED CODE ###

import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = Is()
mat = [[0]*W for i in range(H)]
inp = []
for i in range(H):
    inp.append(list(S()))
for i in range(H):
    t = 0
    for j in range(W):
        if inp[i][j] == ".":
            t += 1
            if j == W-1:
                for k in range(j+1-t,j+1):
                    mat[i][k] += t
        elif inp[i][j] == "#":
            for k in range(j-t,j):
                mat[i][k] += t
            t = 0
#print(*mat)
for j in range(W):
    t = 0
    for i in range(H):
        if inp[i][j] == ".":
            t += 1
            if i == H-1:
                for k in range(i+1-t,i+1):
                    mat[k][j] += t
        elif inp[i][j] == "#":
            for k in range(i-t,i):
                mat[k][j] += t
            t = 0    
#print(*mat)
ans = 0
for e in mat:
    ans = max(ans,max(e))
print(max(0,ans-1))
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
l = []
sum = 0
for i in range(a) :
    l.append(1)
for i in range(b) :
    l.append(0)
for i in range(c) :
    l.append(-1)
l.sort(reverse = True)
for i in range(k) :
    sum += l[i]
print(sum)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
if k <= a :
    print(k)
else :
    m = min(k,a)
    k -= a

    if k <= b :
        print(a)
    else :
        n = min(k,b)
        k -= b
        l = k
        print(1*m+(-1)*l)
### BUGGY CODE ###

n, m = (int(i) for i in input().split())  
x = sorted([int(i) for i in input().split()])


if m > 1:
    x_diff = []
    for i in range(m-1):
        x_diff.append(x[i+1] - x[i])
else:
    x_diff = [0]

for i in range(n-1):
    max_num = max(x_diff)
    max_index = x_diff.index(max_num)
    x_diff[max_index] = 0

print(sum(x_diff))

### FIXED CODE ###

n, m = (int(i) for i in input().split())  
x = sorted([int(i) for i in input().split()])

if m > 1:
    x_diff = []
    for i in range(m-1):
        x_diff.append(x[i+1] - x[i])
else:
    x_diff = [0]

if n > 1:
    x_diff = sorted(x_diff)[:-(n-1)]

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

from fractions import gcd
#from math import gcd
#import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]
lcm=lcms[-1]
sums=[0]
[sums.append( (sums[-1]+lcm//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
### BUGGY CODE ###

s=list(map(str,input()))
A=int(input())
V=[]
S=[]
ct=0
for i in range(1,len(s)+1):
  for j in range((len(s)-(i-1))):
    V.append("".join(s[j:j+i]))
S=sorted(set(V))
#print(S)
print(S[A-1])

### FIXED CODE ###

s=list(map(str,input()))
A=int(input())
V=[]
S=[]
ct=0
for i in range(1,A+1):
  for j in range((len(s)-(i-1))):
    V.append("".join(s[j:j+i]))
S=sorted(set(V))
#print(S)
print(S[A-1])
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    s_ = list(input())
    s.append("".join(sorted(s_)))

s2 = set(s)
cnt = []
for i in s2:
    cnt.append(s.count(i))

ans = 0
for k in range(len(cnt)):
    l = list(range(0,cnt[k]))
    ans += sum(l)
print(ans)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for _ in range(N)]
s.sort()

cnt = 0
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        cnt +=1
        ans += cnt
    else:
        cnt = 0
print(ans)
### BUGGY CODE ###

s  = input()
q = int(input())

#flag=0 でleft, flag=1でrightが先頭
flag = 0
cnt = 0

for _ in range(q):
    lis = list(input().split())
    if lis[0] == "1":
        if flag:
            flag = 0
        else:
            flag = 1
        cnt += 1
    else:
        if lis[1] == '1':
            if flag:
                s = s + lis[2]
            else:
                s = lis[2] + s
        else:
            if flag:
                s = lis[2] + s
            else:
                s = s + lis[2]

if cnt % 2 != 0:
    s = s[::-1]


print(s)

### FIXED CODE ###

from collections import deque

s  = input()
q = int(input())

#flag=0 でleft, flag=1でrightが先頭
flag = 0
cnt = 0
d  = deque(s)

for _ in range(q):
    lis = list(input().split())
    if lis[0] == "1":
        if flag:
            flag = 0
        else:
            flag = 1
        cnt += 1
    else:
        if lis[1] == '1':
            if flag:
                d.append(lis[2])
            else:
                d.appendleft(lis[2])
        else:
            if flag:
                d.appendleft(lis[2])
            else:
                d.append(lis[2])


d = list(d)
if cnt % 2 != 0:
    d = d[::-1]


print(''.join(d))
### BUGGY CODE ###

class RollingHash:
    def __init__(self,text):
        self.mod=10**17+3
        self.p=10007
        self.n=len(text)
        self.table=[0]*(self.n+1)
        for i in range(self.n):
            self.table[i+1]=(self.table[i]*self.p+ord(text[i]))%self.mod
        self.pp=[1]*(self.n+1)
        for i in range(self.n):
            self.pp[i+1]=(self.pp[i]*self.p)%self.mod
    def hash(self, i, j):
        return (self.table[j]-self.table[i]*self.pp[j-i])%self.mod
    def lcp(self, i, j):
        l,r=0,min(self.n-i,self.n-j)
        while r-l>0:
            m=(l+r)//2+1
            if self.hash(i,i+m)==self.hash(j,j+m):
                l=m
            else:
                r=m-1
        return l

n=int(input())
hs=RollingHash(input())
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans=max(ans,min(j-i,hs.lcp(i,j)))
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)
### BUGGY CODE ###

N = input()
datas = []
for _ in range(N):
	data = map(int, raw_input().split(" "))
	datas.append(data)

t_min = datas[0][0]
o_min = datas[0][1]
for _ in range(N-1):
	t_mul = 1
	o_mul = 1
	t = datas[_+1][0]
	o = datas[_+1][1]
	while t_mul*t < t_min:
		t_mul+=1

	while o_mul*o < o_min:
		o_mul+=1

	if t_mul < o_mul:
		t_min = o_mul*t
		o_min = o_mul*o
	else:
		t_min = t_mul*t
		o_min = t_mul*o

print t_min+o_min

### FIXED CODE ###

import math
N = input()
datas = []
for _ in range(N):
	data = map(long, raw_input().split(" "))
	datas.append(data)

t_min = datas[0][0]
o_min = datas[0][1]
for _ in range(N-1):
	t = datas[_+1][0]
	o = datas[_+1][1]
	t_mul = t_min/t + 1 if t_min%t != 0 else t_min/t
	o_mul = o_min/o + 1 if o_min%o != 0 else o_min/o
	if t_mul < o_mul:
		t_min = o_mul*t
		o_min = o_mul*o
	else:
		t_min = t_mul*t
		o_min = t_mul*o

print t_min+o_min
### BUGGY CODE ###

n = int(input())
list_a = [int(x) for x in input().split()]
ans = 1

for i in range(0, n):
    ans *= list_a[i]

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

else: print(ans)

### FIXED CODE ###

n = int(input())
list_a = [int(x) for x in input().split()]
list_a_str = [str(s) for s in list_a]
ans = 1

for i in range(0, n):
    if list_a_str[i] in '0':
        print('0')
        exit()

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

else: print(ans)
### BUGGY CODE ###

import sys
import heapq
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = Counter(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return set(divisors)

heapq.heapify(A)

nums = set()
ans = 0
while A:
    a = heapq.heappop(A)
    a_divs = make_divisors(a)
    if len(nums & a_divs) == 0 and A_counters[a] == 1:
        ans += 1
    nums.add(a)
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = Counter(A)
A.sort()
A_set = set(A)
ans = 0
for a in A:
    if a in A_set:
        if A_counters[a] == 1:
            ans += 1
        for i in range(1, A[-1] // a + 1):
            if a * i in A_set:
                A_set.remove(a * i)
print(ans)
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


rev = [modpow(i, mod - 2) % mod for i in range(10 ** 6 + 1)]
N = int(input())
A = list(map(int, input().split(" ")))
lcm = 1
for a in A:
    lcm = lcm * a * rev[fractions.gcd(lcm, a)]
print(lcm % mod)

ans = 0
for a in A:
    ans += (lcm * rev[a]) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


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

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a

print(ans % mod)
### BUGGY CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
for i in range(1,N):
    if np.min(n[:i]) < n[i] : continue
    else: a+=1   
print(a)

### FIXED CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
pos=0
for i in range(1,N):
    if n[pos] > n[i] :
        a+=1
        pos=i
print(a)
### BUGGY CODE ###

# coding: utf-8
# Your code here!


n = input()

sum_n = 0
for i in n:
    sum_n += int(n)
    
if sum_n % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# coding: utf-8
# Your code here!


n = int(input())

if n % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n, m = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = 10**9+7
ans = 0
for i in range(n-1):
  for j in range(m-1):
    t = (X[i+1]-X[i]) * (Y[j+1]-Y[j])
    t %= MOD
    t *= (n-i-1)*(i+1)
    t %= MOD
    t *= (m-j-1)*(j+1)
    t %= MOD
    ans += t
    ans %= MOD
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = 10**9+7
sx, sy = 0, 0
for i in range(n):
  t = 2*i+1-n
  t *= X[i]
  t %= MOD
  sx += t
  sx %= MOD
for j in range(m):
  t = 2*j+1-m
  t *= Y[j]
  t %= MOD
  sy += t
  sy %= MOD
print(sx*sy%MOD)