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

m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		for c in range(m):
			if S[r][c] == 0: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

### FIXED CODE ###

def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N)]


for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N-1][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]

# Wの最大が大きすぎて計算間に合わないので最大最小変換を行う
# dp[i+1][j]：i番目までのアイテムをナップザックに入れられるとき、価値がjとなる最小の重み
dp = [{} for i in range(N+1)]
dp[0][0] = 0


for i, (w,v) in enumerate(wv):
    for v0, w0 in dp[i].items(): # dictのキーと値に対してfor、i-1番目までのアイテムについて考える
        if v0 in dp[i+1]: # 
            dp[i+1][v0] = min(dp[i+1][v0], w0) # 同じ価値でさらに軽いものがある場合はそれを最小の重みに指定
        else:
            dp[i+1][v0] = w0 # 価値v0のものが今までのアイテムになければ、それを最小の重みに指定
        
        if w0+w > W: # 或る価値に対する最小重みに、現在のアイテムの重みを足して上限を超える場合は、今の価値についてそのアイテムは選択対象外
            continue # 
        if v0+v in dp[i+1]: # 今までの価値+新しく選んだものの価値 がi番目までのアイテムを選んだ時に既に存在する場合
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w


print(max(dp[-1].keys())) # 全部選んでいいときに価値として起こりうるものの最大
### BUGGY CODE ###

import math

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

balls = [0]*n
for a in A:
    balls[a-1] += 1

tei = math.factorial(2)
ball_permu = [0]*n
ball_permu_target = [0]*n
fac = [-1]*n
for i in range(n):
    if balls[i] < 2:
        ball_permu[i] = 0
    else:
        if fac[balls[i]-1] == -1:
            ball_permu[i] = math.factorial(balls[i])//(math.factorial(balls[i]-2)*tei)
            fac[balls[i]-1] = ball_permu[i]
        else:
            ball_permu[i]=fac[balls[i]-1]

    ball = balls[i]-1
    if ball < 2:
        ball_permu_target[i] = 0
    else:
        if fac[ball-1] == -1:
            ball_permu_target[i] = math.factorial(ball)//(math.factorial(ball-2)*tei)
            fac[ball-1] = ball_permu_target[i]
        else:
            ball_permu_target[i]=fac[ball-1]

ball_sum = sum(ball_permu)
for a in A:
    ans = ball_sum-ball_permu[a-1]+ball_permu_target[a-1]
    print(ans)


### FIXED CODE ###

from collections import Counter

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

C = Counter(A)
a_sum = 0
for i in C.values():
    a_sum += i*(i-1)//2

for a in A:
    k = C[a]
    print(a_sum-(k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

X,Y,Z,K=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
a=b=c=0
L=[[0,0,0]]
for k in range(K):
    maximum=0
    index=-1
    for i,l in enumerate(L):
        if A[l[0]]+B[l[1]]+C[l[2]]>maximum:
            maximum=A[l[0]]+B[l[1]]+C[l[2]]
            index=i
    if len(A)>L[index][0]+1 and [L[index][0]+1,L[index][1],L[index][2]] not in L: 
        L.append([L[index][0]+1,L[index][1],L[index][2]])
    if len(B)>L[index][1]+1 and [L[index][0],L[index][1]+1,L[index][2]] not in L:
        L.append([L[index][0],L[index][1]+1,L[index][2]])
    if len(C)>L[index][2]+1 and [L[index][0],L[index][1],L[index][2]+1] not in L:
        L.append([L[index][0],L[index][1],L[index][2]+1])
    print(A[L[index][0]]+B[L[index][1]]+C[L[index][2]])
    del L[index]

### FIXED CODE ###

x,y,z,k=map(int, input().split())
a=sorted(list(map(int, input().split())),reverse=True)
b=sorted(list(map(int, input().split())),reverse=True)
c=sorted(list(map(int, input().split())),reverse=True)

from heapq import heapify,heappop,heappush
q=[]
heappush(q,(-a[0]-b[0]-c[0],(0,0,0)))
used={(0,0,0):True}
for i in range(k):
    if q[0][1][0]+1<x and (q[0][1][0]+1,q[0][1][1],q[0][1][2]) not in used:
        heappush(q,(-a[q[0][1][0]+1]-b[q[0][1][1]]-c[q[0][1][2]],(q[0][1][0]+1,q[0][1][1],q[0][1][2])))
        used[(q[0][1][0]+1,q[0][1][1],q[0][1][2])]=True
    if q[0][1][1]+1<y and (q[0][1][0],q[0][1][1]+1,q[0][1][2]) not in used:
        heappush(q,(-a[q[0][1][0]]-b[q[0][1][1]+1]-c[q[0][1][2]],(q[0][1][0],q[0][1][1]+1,q[0][1][2])))
        used[(q[0][1][0],q[0][1][1]+1,q[0][1][2])]=True
    if q[0][1][2]+1<z and (q[0][1][0],q[0][1][1],q[0][1][2]+1) not in used:
        heappush(q,(-a[q[0][1][0]]-b[q[0][1][1]]-c[q[0][1][2]+1],(q[0][1][0],q[0][1][1],q[0][1][2]+1)))
        used[(q[0][1][0],q[0][1][1],q[0][1][2]+1)]=True
    print(-heappop(q)[0])
### BUGGY CODE ###

import numpy as np
def main():
    MOD = 10 ** 9 + 7
    S = input()
    N = len(S)
    mod13 = [np.zeros((13,), dtype=np.int64) for _ in range(N + 1)]
    mod13[0][0] = 1
    exponent = 1
    for i in range(1, N + 1):
        c = S[-i]
        if c == "?":
            for n in range(10):
                m = n * exponent % 13
                mod13[i] += np.roll(mod13[i - 1], m)
        else:
            m = int(c) * exponent % 13
            mod13[i] += np.roll(mod13[i - 1], m)
        exponent = exponent * 10 % 13
        mod13[i] %= MOD
    print(mod13[N][5])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    S = input()
    N = len(S)
    mod13 = [[0] * 13 for _ in range(N + 1)]
    mod13[0][0] = 1
    exponent = 1
    for i in range(1, N + 1):
        c = S[-i]
        if c == "?":
            for n in range(10):
                m = n * exponent % 13
                for r in range(13):
                    mod13[i][(r + m) % 13] += mod13[i - 1][r]
        else:
            m = int(c) * exponent % 13
            for r in range(13):
                mod13[i][(r + m) % 13] = mod13[i - 1][r]
        exponent = exponent * 10 % 13
        for r in range(13):
            mod13[i][r] %= MOD
    print(mod13[N][5])

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

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = readline().decode().rstrip()
q = int(readline())

head = ""
tail = ""
flip = 0
for _ in range(q):
    que = readline().decode().split()
    if len(que) == 1:
        head, tail = tail[::-1], head[::-1]
        flip += 1

    else:
        if que[1] == '1':

            head = ''.join([que[2], head])

        else:
            tail = ''.join([tail, que[2]])

if flip % 2 == 0:
    print(''.join([head, S, tail]))
else:
    print(''.join([head, S[::-1], tail]))


### FIXED CODE ###

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = readline().decode().rstrip()
q = int(readline())

head = ""
tail = ""
flip = 0
for _ in range(q):
    que = readline().decode().split()
    if len(que) == 1:
        flip += 1

    else:
        if que[1] == '1':
            if flip % 2 == 0:

                head = ''.join([que[2], head])
            else:
                tail = ''.join([tail, que[2]])

        else:
            if flip % 2 == 0:

                tail = ''.join([tail, que[2]])
            else:
                head = ''.join([que[2], head])

if flip % 2 == 0:
    print(''.join([head, S, tail]))
else:
    print(''.join([tail[::-1], S[::-1], head[::-1]]))
### BUGGY CODE ###

import numpy as np

N = int(input())
S = np.array([0 if a == 'E' else 1 for a in input()])

ans = N
for i in range(N):
    ans = min(ans, np.count_nonzero(S[:i]) + np.count_nonzero(S[i+1:]-1))

print(ans)

### FIXED CODE ###

N = int(input())
S = [0 if a == 'E' else 1 for a in input()]
Sp = [S[0]]
for i in range(1, N):
    Sp.append(Sp[-1]+S[i])

max = Sp[-1]
ans = N - max
for i in range(1, N):
    ans = min(abs(Sp[i-1]) + abs(N-(i+1)-max+Sp[i]), ans)

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

n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=0
s=0

for i in range(k,n+1):
  p = l[i-k:i]
  s = sum([p[j]*(p[j]+1)/2/p[j] for j in range(k)])
  
  if ans < s:
    ans = s
  s=0
  
print(ans)

### FIXED CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
s = sum(p[:k])
m = s

for i in range(n-k):
  s = s-p[i]+p[i+k]
  if m < s:
    m = s
print((m+k)/2)
### BUGGY CODE ###

L, R = (int(item) for item in input().split())

m=2020
ii=0
jj=0
for i in range(L,R+1):
  for j in range(i+1,R+1):
    if m > (i*j % 2019):
      m = (i*j % 2019)
      ii=i
      jj=j      
print(m)

### FIXED CODE ###

L, R = (int(item) for item in input().split())

m=2020
if R-L > 2020:
  print(0)
else:
  for i in range(L,R+1):
    for j in range(i+1,R+1):
      mm = i*j % 2019
      if m > mm:
        m = (i*j % 2019)
  print(m)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = 0
while (1):
   b = [x % 2 for x in a]
   if (0 not in b):
      break

   c = b.index(0)
   a = [int(a[i]/2) if i == c else a[i] for i in range(n)]
   ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = 0
while (1):
   b = [x % 2 for x in a]
   ans += b.count(0)
   if (0 not in b):
      break

   a = [int(a[i]/2) if b[i]==0 else a[i] for i in range(n)]

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

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]

dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            elif k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)

### FIXED CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
def count(n, a):
    c = 0
    for i in range(len(a)):
        if a[i] == n:
            c += 1
    return c
for j in range(N):
    print(count(j+1, A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
buka = list()
for i in range(N):
    buka.append(0)
for j in range(len(A)):
    buka[A[j]-1] += 1
for k in range(len(buka)):
    print(buka[k])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC77 C

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 i in a:
    s = 0
    x = bisect.bisect_right(b,i)
    for j in b[x:]:
        y = bisect.bisect_right(c,j)
        ans += n-y
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC77 C

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 i in b:
    x = bisect.bisect_left(a,i)
    y = bisect.bisect_right(c,i)
    ans += x*(n-y)
print(ans)
### BUGGY CODE ###

MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1

for i in range(K):
    res *= A[~i]

if res > 0:
    print(res % MOD)

else:
    tmp1 = res
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 //= A[minneg]
    tmp2 = res
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        tmp2 *= A[maxneg]
        tmp2 //= A[minpos]
    if tmp1 > 0 or tmp2 > 0:
        print(max(tmp1, tmp2) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
            print(res % MOD)

### FIXED CODE ###

MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1
sign = 1

for i in range(K):
    res *= A[~i]
    res %= MOD
    if A[~i] < 0:
        sign *= -1

    if A[~i] == 0:
        sign = 0

if sign == 1:
    print(res % MOD)

elif sign == 0:
    print(0)

else:
    flag1 = False
    tmp1 = -1
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            flag1 = True
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 /= A[minneg]
    flag2 = False
    tmp2 = -1
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        flag2 = True
        tmp2 *= A[maxneg]
        tmp2 /= A[minpos]
    if flag1 and flag2:
        if A[maxpos] * A[minpos] > A[maxneg] * A[minneg]:
            print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
        else:
            print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    elif flag1:
        print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
    elif flag2:
        print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
                res %= MOD
            print(res % MOD)
### BUGGY CODE ###

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

b_init = sum(A)//N - N*(N+1)//(2*N)

while 1:
    #calculate sadness
    sadness = sum([abs(A[i] - (b_init+(i+1))) for i in range(N)])
    sadness_plus1 = sum([abs(A[i] - (b_init+1+(i+1))) for i in range(N)])
    sadness_minus1 = sum([abs(A[i] - (b_init-1+(i+1))) for i in range(N)])
    
    # initial equal ans
    if sadness <= sadness_plus1 and sadness <= sadness_minus1:
        print(sadness)
        break
    
    # right way
    if sadness_plus1 < sadness:
        sad_righter = sadness_plus1
        b = b_init
        while sad_righter <= sadness:
            b+=1
            sadness = sad_righter
            sad_righter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break
    
    # left way
    if sadness_minus1 < sadness:
        sad_lefter = sadness_minus1
        b = b_init
        while sad_lefter <= sadness:
            b-=1
            sadness = sad_lefter
            sad_lefter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break

### FIXED CODE ###

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

if N==1:
    print(0)
else:
    B = [A[i]-i for i in range(N)]
    B.sort()
    b_pl = B[N//2]
    b_mn = B[N//2-1]
    
    sadness_pl = sum([abs(B[i]-b_pl) for i in range(N)])
    sadness_mn = sum([abs(B[i]-b_mn) for i in range(N)])
    
    print(min(sadness_pl, sadness_mn))
### BUGGY CODE ###

h,n = map(int,input().split())
li2=[input() for i in range(n)]
ab = []
for i in range(n):
    ab.append( [int(x.strip()) for x in li2[i].split()])

#dp　横を合計攻撃力　中身を最小魔力とする
dp = [100000000] * (h + 10 ** 4 + 1)
#hpを0減らすのに必要な魔力は0
dp[0] = 0

for i in range(h):
    if dp[i] == 100000000:#初期値の場合は更新しない
        continue

    for a, b in ab:#aがアタック bが使用魔力
        t = dp[i] + b #n番目の呪文を使った時、合計の魔力はtとなる
        if t < dp[i + a]: #今入っている魔力が新しい魔力よりも高いとき更新
            dp[i + a] = t
#print(dp)
print(min(dp[h:]))

### FIXED CODE ###

a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in x)

print(dp[HP])
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    query = input()
    if query[0] == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
inv = False
pr, su = deque(), deque()
for _ in range(q):
    query = input()
    if query[0] == '1':
        inv = not inv
    else:
        _, f, c = query.split()
        if inv:
            if f == '1': su.append(c)
            else: pr.append(c)
        else:
            if f == '1': pr.append(c)
            else: su.append(c)
ans = ''.join(pr)[::-1] + s + ''.join(su)
print(ans[::-1] if inv else ans)
### BUGGY CODE ###

L, R = map(int, input().split())

min = 2*1000000000

for i in range(L,R):
    for j in range(i+1,R+1):
        if min > ((i % 2019) * (j % 2019))%2019:
            min = ((i % 2019) * (j % 2019))%2019

print(min)

### FIXED CODE ###

L, R = map(int, input().split())

min = 2*1000000000

if R - L > 2019:
  R = L + 2019

for i in range(L,R):
    for j in range(i+1,R+1):
        if min > ((i % 2019) * (j % 2019))%2019:
            min = ((i % 2019) * (j % 2019))%2019

print(min)
### BUGGY CODE ###

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    #input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)


### FIXED CODE ###

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = [0 for _ in range(max(A) + 5)]
for i in range(N):
  if ans[A[i]] == 0:
    for j in range(0, max(A) + 5, A[i]):
      ans[j] += 1
  else:
    ans[A[i]] += 1
cnt = 0
for a in A:
  if ans[a] == 1:
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1] + 1
ans = [0]*max_A
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max_A, i):
      ans[j] = 2
print(ans.count(1))
### BUGGY CODE ###

from  fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM // A[i]

    ans %= MOD
print(ans)

### FIXED CODE ###

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM * pow(A[i], MOD - 2, MOD)
print(ans%MOD)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=1000000007
ans=0
product=1
for i in range (n-1):        
    for j in range(i+1,n):
        product=((a[i])*(a[j]%mod))%mod
        ans=(ans+product)
        if ans>mod:
            ans=ans%mod

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=1000000007
ans=0
s=0
for i in range (n-1):
    if i ==0:
        for j in range(i+1,n):
            s=(s+a[j])%mod
    else:
        s-=a[i]
    ans=(ans+(a[i]*(s))%mod)%mod

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

import numpy as np
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = np.full((N,N),np.inf)
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(int(ans))


### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = [[float("INF")]*N for _ in range(N)]
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

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

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
b = copy.deepcopy(a)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    B = b[np.where(M % (i+1) == 0)]
    if np.sum(B) % 2  == 0:
        b[i] = 0
    else:
        b[i] = 1
        
ans = np.where(b == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))

### FIXED CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[i::i+1]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))