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

#n: id card
#m: gate
n, m = map(int, input().split())
data = [0 for i in range(n+1)]
ans = 0

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r+1):
        data[j] += 1

for i in range(1, n+1):
    if data[i] == m:
        ans += 1

print(ans)

### FIXED CODE ###

#n: id card
#m: gate
n, m = map(int, input().split())
data = [0 for i in range(n+1)]

for i in range(m):
    l, r = map(int, input().split())
    data[l-1] += 1
    data[r] -= 1

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

print(data.count(m))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)
### BUGGY CODE ###

def main():
    K,S = [int(x) for x in input().split()]
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if S == x+y+z:
                    cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    K,S = [int(x) for x in input().split()]
    cnt = 0
    for x in range(K+1):
        if x > S:
            break
        for y in range(K+1):
            if x+y > S:
                break
            z = S-(x+y)
            if z < 0 or z > K:
                continue
            # print(x,y,z)
            if S == x+y+z:
                cnt += 1
    print(cnt)

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

def main():
    n, k = list(map(int, input().split()))
    daice = list(map(int, input().split()))
    sum_val = 0
    kitai = []
    for i in range(0, len(daice) - k + 1):
        tmp = daice[i:i + k]
        if sum(tmp) >= sum_val:
            sum_val = sum(tmp)
            kitai = tmp
    ans = 0
    for v in kitai:
        sumt = 0
        for i in range(1, v + 1):
            sumt += i * (1 / v)
        ans += sumt
    print(ans)




if __name__ == '__main__':
    main()

### FIXED CODE ###


url = "https://atcoder.jp//contests/abc154/tasks/abc154_d"

def search_ind(lis, k):
    tmp = sum(lis[0:k])
    m = tmp
    inds = [0, k - 1]
    for i in range(0, len(lis) - k):
        tmp = tmp - lis[i] + lis[i + k]
        # print(tmp, lis[i + k])
        if tmp > m:
            inds = [i + 1, i + k]
            m = tmp
    return inds

def main():
    n, k = list(map(int, input().split()))
    daice = list(map(int, input().split()))
    f, t = search_ind(daice, k)
    kitai = daice[f:t + 1]
    ans = 0
    for v in kitai:
        sumt = 0
        for i in range(1, v + 1):
            sumt += i * (1 / v)
        ans += sumt
    print(ans)




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

from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = input()
    if command[0] == "i":
        que.appendleft(command[7:])
    elif "deleteFirst" in command:
        que.popleft()
    elif "deleteLast" in command:
        que.pop()
    else:
        try:
            que.remove(command[7:])
        except:
            pass
print(" ".join(que))

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = sys.stdin.readline()[:-1]
    if command[0] == "i":
        que.appendleft(command[7:])
    elif command[6] == " ":
        try:
            que.remove(command[7:])
        except:
            pass
    elif command[6] == "F":
        que.popleft()
    else:
        que.pop()
print(*que)
### BUGGY CODE ###

from itertools import product

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
abcd.sort()

ans = 0
for bit in product([0, 1], repeat=q):
    tmp = [1] * (n + 1)
    bl = [0] * (n + 1)
    f = True
    for i, j in enumerate(bit):
        if j == 1:
            if bl[abcd[i][1]] == 1:
                if bl[abcd[i][0]] == 1:
                    if tmp[abcd[i][0]] != tmp[abcd[i][1]] - abcd[i][2]:
                        f = False
                        break
                else:
                    tmp[abcd[i][0]] = tmp[abcd[i][1]] - abcd[i][2]
                    bl[abcd[i][0]] = 1
            else:
                tmp[abcd[i][1]] = tmp[abcd[i][0]] + abcd[i][2]
                bl[abcd[i][1]] = 1
    pre = tmp[0]
    for i in range(1, n):
        if bl[i] == False:
            tmp[i] = tmp[i-1]
        if pre > tmp[i]:
            f = False
            break
        pre = tmp[i]
    if f:
        cnt = 0
        for i, j in enumerate(bit):
            if j == 1:
                cnt += abcd[i][3]
        ans = max(ans, cnt)
print(ans)

### FIXED CODE ###

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for a in range(1, m + 1):
    for b in range(a, m + 1):
        for c in range(b, m + 1):
            for d in range(c, m + 1):
                for e in range(d, m + 1):
                    for f in range(e, m + 1):
                        for g in range(f, m + 1):
                            for h in range(g, m + 1):
                                for i in range(h, m + 1):
                                    for j in range(i, m + 1):
                                        s = [0, a, b, c, d, e, f, g, h, i, j]
                                        cnt = 0
                                        for w, x, y, z in abcd:
                                            if s[x] - s[w] == y:
                                                cnt += z
                                        ans = max(cnt, ans)
print(ans)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

b = 1
for i in a:
    b = b * i // gcd(b, i)

ans = 0
for i in a:
    ans += b // i

print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
p = 10 ** 9 + 7

def pr(x):
    a=[]
    i=2
    while True:
        if x % i == 0:
            j=0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x,1))
    return a
c = {}
for i in a:
    d = pr(i)
    for j in d:
        if j[0] in c:
            c[j[0]] = max(c[j[0]], j[1])
        else:
            c[j[0]] = j[1]

b = 1
for i in c:
    b *= pow(i, c[i], p)
    b %= p
ans = 0
for i in a:
    ans += b * pow(i, p - 2, p)
    ans %= p
print(ans)
### BUGGY CODE ###


def examD():
    N = I()
    a = LI();  b = LI()
    cura = [0]*N; curb=[0]*N
    ansC = [0]*29
    for i in range(29):
        T = (2 ** i)
        for j in range(N):
            curb[j] = b[j]%(2**(i+1))
        curb.sort()
        for j in range(N):
            cura[j] = a[j]%(2**(i+1))
            loc1 = T - cura[j]
            loc3 = 2 * T - cura[j]
            loc2 = 3 * T - cura[j]
            cur = (bisect.bisect_left(curb, loc1)-bisect.bisect_left(curb, loc2)\
                + bisect.bisect_left(curb, loc3))+N
            ansC[i] = (ansC[i]+cur)%2
#    print(ansC)
    ans = 0
    for i in range(29):
        ans += ansC[i]*(2**i)
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


### FIXED CODE ###

def examD():
    N = I()
    a = LI();  b = LI()
    cura = [0]*N; curb=[0]*N
    ans = 0
    for i in range(28,-1,-1):
        T = (2 ** i)
        for j in range(N):
            cura[j] = a[j]%(2**(i+1))
            curb[j] = b[j]%(2**(i+1))
        curb.sort()
        cura.sort(reverse=1)
        f, l1, r1, l2 = 0, 0, 0, 0
        for x in cura:
            while l1 < N and x + curb[l1] < T:
                l1 += 1
            while r1 < N and x + curb[r1] < 2 * T:
                r1 += 1
            while l2 < N and x + curb[l2] < 3 * T:
                l2 += 1
            f += N - l2 + r1 - l1
        ans += T * (f & 1)
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
    
val = L[0]
for i in range(1,n):
    val=gcd(L[i],val)
if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')



### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')
### BUGGY CODE ###

from math import factorial
import collections
import copy
def cmb(n,r):
  if n-r<0:
    return 0
  return factorial(n) // factorial(r) // factorial(n - r)
n=int(input())
a=list(map(int,input().split()))
ccc=[]
for i in range(n):
  ccc.append(cmb(i,2))

c=collections.Counter(a)
for aa in a:
  t=copy.copy(c)
  o=0
  t[aa]-=1
  for i in t.values():
    o+=ccc[i]
  print(o)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
数え=[0]*N
for i in A:
  数え[i-1]+=1
前者=0
for i in 数え:
  前者+=i*(i-1)//2
for i in A:
  後者=数え[i-1]-1
  print(前者-後者)
### BUGGY CODE ###

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > 10**6:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > A[-1]:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
# 愚直な回答
ans = 0
for i in range(0, N-1):
    for j in range(i+1, N):
        ans += A[i]^A[j]
print(ans % INF)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)
### BUGGY CODE ###

Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]
b_append = b.append
for i in range(1,N+1):
    if i in a:
        b.append(0)
        continue
    if i == 1:
        b.append(1)
        continue
    b.append(b[i-1]+b[i-2])
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

### FIXED CODE ###

Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])
### BUGGY CODE ###

import numpy as np
import itertools

H, W, K = map(int, input().split())
S = np.array([[int(s) for s in input()] for _ in range(H)])

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = np.copy(S[0]).reshape(1, -1)
    for h in range(H - 1):
        if t[h]:
            lst = np.vstack([lst, S[h + 1]])
        else:
            lst[-1] = lst[-1] + S[h + 1]
    L = len(lst)
    sum_lst = np.zeros(L)
    for w in range(W):
        lst_w = lst[:, w]
        if lst_w.max() > K:
            break
        lst_s = sum_lst + lst_w
        if lst_s.max() > K:
            cnt += 1
            sum_lst = lst_w
        else:
            sum_lst = lst_s
    else:
        ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###


n,m = list(map(int,input().split()))
d = []
spr = [[False]*m]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      print(sum([1 for i in range(n) if bit & 1<<i]))
      exit()




### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

import sys
import fractions
input=sys.stdin.readline

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
k = 0
for i in a:
    for j in b:
        if j <= i:
            continue
        for k in range(len(c)):
            if j < c[k]:
                ans += (n - k)
                break
print(ans)


### FIXED CODE ###

import sys
import fractions
import bisect
input=sys.stdin.readline

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
k = 0
for j in b:
    ai = bisect.bisect_left(a, j)
    ci = n - bisect.bisect_right(c, j)
    ans += ai * ci
print(ans)
### BUGGY CODE ###

def maximum_profit(n):
    max_profit = min(n) - max(n)
    for i in range(1, len(n)):
        x = max(n[i:]) - n[i-1]
        if max_profit < x:
            max_profit = x
    return max_profit

if __name__ == '__main__':
    n = int(input())
    numbers = [int(input()) for i in range(0, n)]
    print(maximum_profit(numbers))



### FIXED CODE ###

def maximum_profit(n):
    maxv = min(n) - max(n)
    minv = n[0]
    for i in range(1, len(n)):
        maxv = n[i] - minv if maxv < n[i] - minv else maxv
        minv = n[i]        if minv > n[i]        else minv
    return maxv
if __name__ == '__main__':
    n = int(input())
    numbers = [int(input()) for i in range(0, n)]
    print(maximum_profit(numbers))
### BUGGY CODE ###

from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [0]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    #uf[node-1] = ufid
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] != 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = dic[str(now_node)]
        for tgt in target:
            if uf[tgt-1] == 0:
                q.put(tgt)
    return leng

len_ls = []
var = 1
for i in range(1,N+1):
    if uf[i-1] == 0:
        # 連結判定
        leng = BFS(var, dic, i)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)


### FIXED CODE ###

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)
### BUGGY CODE ###

from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*(a[i]//gcd(lcm,a[i]))*gcd(lcm,a[i])
ans=0
for i in range(n):
  ans+=lcm*inv[a[i]]%mod
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*a[i]
ans=0
lcm%=mod
for i in range(n):
  ans=(ans+lcm*inv[a[i]])%mod
print(ans%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
ans = [A[-1]]
com = 0
for i in range(2,N+1) :
    com += ans[-1]
    del ans[-1]
    ans.append(A[-i])
    ans.append(A[-i])
    ans = sorted(ans)
print(com)


    
    
    


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
ans = 0
for i in range(1,N) :
    ans += A[N-1 - i//2 ]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
x=[int(input()) for _ in range(m)]
f=[0]*(n+1)
f[0]=1
for i in range(1,n+1):
  f[i]=(f[i-1]+f[i-2])%(10**9+7)
  if i in x:
    f[i]=0
print(f[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
x=set([int(input()) for _ in range(m)])
f=[0]*(n+1)
f[0]=1
for i in range(1,n+1):
  f[i]=f[i-1]+f[i-2]
  if i in x:
    f[i]=0
print(f[n]%(10**9+7))