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

N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)

uf = [-1] * N
values = []
for i in range(M - 1, -1, -1):
    a = A[i]
    b = B[i]

    cur_a = a
    while 0 <= uf[cur_a]:
        cur_a = uf[cur_a]
    num_a = -uf[cur_a]
    root_a = cur_a

    cur_b = b
    while 0 <= uf[cur_b]:
        cur_b = uf[cur_b]
    num_b = -uf[cur_b]
    root_b = cur_b

    if root_a != root_b:
        values.append(num_a * num_b)

        uf[root_b] += uf[root_a]
        cur = uf[root_a]
        uf[root_a] = root_b
        while 0 <= cur and 0 <= uf[cur]:
            nxt = uf[cur]
            uf[cur] = root_b
            cur = nxt
    else:
        values.append(0)

total = 0
for v in reversed(values):
    total += v
    print(total)


### FIXED CODE ###

import io
import sys

lines = sys.stdin.read().splitlines()[::-1]


def readline():
    return lines.pop()


N, M = map(int, readline().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, readline().split())
    A.append(a - 1)
    B.append(b - 1)

uf = [-1] * N
values = []
for i in range(M - 1, -1, -1):
    a = A[i]
    b = B[i]

    cur = a
    while 0 <= uf[cur]:
        cur = uf[cur]
    num_a = -uf[cur]
    root_a = cur
    cur = a
    while 0 <= uf[cur]:
        nxt = uf[cur]
        uf[cur] = root_a
        cur = nxt

    cur = b
    while 0 <= uf[cur]:
        cur = uf[cur]
    num_b = -uf[cur]
    root_b = cur
    cur = b
    while 0 <= uf[cur]:
        nxt = uf[cur]
        uf[cur] = root_b
        cur = nxt

    if root_a != root_b:
        values.append(num_a * num_b)

        if num_a < num_b:
            uf[root_b] += uf[root_a]
            cur = uf[root_a]
            uf[root_a] = root_b
            while 0 <= cur and 0 <= uf[cur]:
                nxt = uf[cur]
                uf[cur] = root_b
                cur = nxt
        else:
            uf[root_a] += uf[root_b]
            cur = uf[root_b]
            uf[root_b] = root_a
            while 0 <= cur and 0 <= uf[cur]:
                nxt = uf[cur]
                uf[cur] = root_a
                cur = nxt
    else:
        values.append(0)

total = 0
out = io.StringIO()
for v in reversed(values):
    total += v
    print(total, file=out)
print(out.getvalue())
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def factorization(n):
    if n == 1:
        return [[1,0]]
    else:
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([n, 1])

        return arr

def main():
    N = NI()
    ans = 0
    for C in range(1,N):
        cnt = 1
        AXB = N-C
        factri = factorization(AXB)
        for x in range(len(factri)):
            cnt = cnt * (factri[x][1]+1)
        ans += cnt
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table


def main():
    N = NI()
    print(sum(num_divisors_table(N-1)))

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

x = int(input())
sign = ((1,1),(1,-1),(-1,1),(-1,-1))
isloop=True
for a in range(10**5):
    if(isloop==False):
        break
    for b in range(10**5):
        if(isloop==False):
            break
        for s1,s2 in sign:
            if(isloop==False):
                break
            a1 = s1*a
            b1 = s2*b
            if((a1**5)==(x+b1**5)):
                print(a1,b1)
                isloop=False
                break
            
        

### FIXED CODE ###

x = int(input())
sign = ((1,1),(1,-1),(-1,1),(-1,-1))
isloop=True
for a in range(10**3):
    if(isloop==False):
        break
    for b in range(10**3):
        if(isloop==False):
            break
        for s1,s2 in sign:
            if(isloop==False):
                break
            a1 = s1*a
            b1 = s2*b
            if((a1**5)==(x+b1**5)):
                print(a1,b1)
                isloop=False
                break
### BUGGY CODE ###

n = int(raw_input())
a = raw_input().split()

b = []
for i in range(n):
  if i % 2:
    b.append(a[i])
  else:
    b.insert(0, a[i])

if n % 2:
  print " ".join(b)
else:
  print " ".join(b[::-1])


### FIXED CODE ###

n = int(raw_input())
a = raw_input().split()

b = []
c = []
for i in range(n):
  if i % 2:
    b.append(a[i])
  else:
    # b.insert(0, a[i])
    c.append(a[i])

b = c[::-1] + b

if n % 2:
  print " ".join(b)
else:
  print " ".join(b[::-1])
### BUGGY CODE ###

def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans


n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
for i in range(n-1):
  b = 0
  for j in range(i+1,n):
    b += S[j]
    b = b % divisor
  a = S[i]
  tot += multmod(a,b,divisor)
  if tot >= divisor:
    tot = tot % divisor
    
print(tot)

### FIXED CODE ###

def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
arr_sum = sum(S) #% divisor
arr_ssq = arr_sum*arr_sum #% divisor
isq_sum = 0
for i in range(n):
  isq_sum += S[i]*S[i] #% divisor
  
#isq_sum = isq_sum % divisor
tot = (arr_ssq - isq_sum)//2 % divisor

print(tot)
### BUGGY CODE ###

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

for i in range(1,len(A)+1):
  R += str(A.index(i)+1) + ' '

print(R)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
lst = [0]*len(A)
cnt = 1

for i in A:
  lst[i-1] = str(cnt)
  cnt += 1

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

#input
N, M = map(int, input().split())
s = [0] * M
t = [0] * M
for i in range(M):
    s[i], t[i] = map(int, input().split())

#output
#（便宜的に地点から-1としておく）
u = [[]] * N
for v in s:
    u[v-1] = [t-1 for i, t in enumerate(t) if s[i] == v]

#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for v in range(N):
    for i in range(v):
        if v in u[i]:
            p[v] += p[i]/len(u[i])

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for v in reversed(range(N)):
    for i in u[v]:
        q[v] += (1 + q[i])/len(u[v])

v = [0] * N
for i in range(N):
    a = len(u[i])
    if a > 1:
        b = max([q[e] for e in u[i]])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)
        
print(q[0]+min(v))

### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
u = [[] for i in range(N-1)]
#（便宜的に地点から-1としておく）
for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)

#output
#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for x, y in enumerate(u):
    for z in y:
        p[z] += p[x]/len(y)

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for x, y in list(enumerate(u))[::-1]:
    q[x] = sum(q[z] for z in y)/len(y) + 1

v = [0] * N
for i in range(N-1):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))
### BUGGY CODE ###

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

ans_list = [[1, 0] for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now][1] >= 2:
        continue
    elif ans_list[now][1] == 1:
        ans_list[now][1] = 2
    else:
        ans_list[now][1] = 1
    for j in range(2*now, 1000001, now):
        ans_list[j][0] = 0

count = 0
for i in range(N):
    now = A[i]
    if ans_list[now][0] == 1 and ans_list[now][1] == 1:
        count += 1
        
print(count)

### FIXED CODE ###

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

num = [1 for i in range(1000001)]
ans_list = [0 for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now] == 2:
        continue
    elif ans_list[now] == 1:
        ans_list[now] = 2
    else:
        ans_list[now] = 1
    for j in range(2*now, 1000001, now):
        num[j] = 0

count = 0
for i in range(N):
    now = A[i]
    if num[now] == 1 and ans_list[now] == 1:
        count += 1
        
print(count)
### BUGGY CODE ###

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

### FIXED CODE ###

#import sys
#def input():
#  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])
### BUGGY CODE ###

a, b ,c = map(int,input().split(" "))
ap =[]
ap = list(map(int,input().split(" ")))
bp =[]
bp = list(map(int,input().split(" ")))
lowest = 10000000
for i in ap:
    for j in bp:
        lowest = min(lowest,i+j)
for _ in range(c):
    x, y ,z = map(int,input().split(" "))
    dis = ap[x-1] + bp[y-1] - z
    lowest = min(lowest,dis)
print(lowest)

### FIXED CODE ###

a, b ,c = map(int,input().split(" "))
ap =[]
ap = list(map(int,input().split(" ")))
bp =[]
bp = list(map(int,input().split(" ")))
lowest = 10000000
ma = min(ap)
mb = min(bp)
lowest = ma +mb
for _ in range(c):
    x, y ,z = map(int,input().split(" "))
    dis = ap[x-1] + bp[y-1] - z
    lowest = min(lowest,dis)
print(lowest)
### BUGGY CODE ###

import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
csum = list(np.cumsum(a_ls))
ans = 0

for start in range(1,n):
    for end in range(start, n):
        if csum[end] - csum[start-1] == 0:
            ans += 1
for i in range(n):
    if csum[i] == 0:
        ans += 1
print(ans)



### FIXED CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a_ls = list(map(int, input().split()))
a_csum = [0] * n
now = 0
for i in range(n):
    now += a_ls[i]
    a_csum[i] = now
a_csum.append(0)
a_csum.sort()
ans = 0
now = 0
for i in range(n):
    if a_csum[i] == a_csum[i+1]:
        now += 1
    else:
        if now > 0:
            ans += combinations_count(now+1,2)
        now = 0
if now > 0:
    ans += combinations_count(now+1,2)
print(ans)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

ans = ans if ans <= 10 ** 18 else -1
print(ans)

### FIXED CODE ###

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

ans = 1
for a in A:
    ans *= a

    if ans > 10 ** 18:
        break
ans = 0 if 0 in A else ans
ans = ans if ans <= 10 ** 18 else -1
print(ans)
### BUGGY CODE ###

vs = set()
def dfs_w(d, stack):
    depthh = [-1] + [0]*N
    path = [0]
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)
            pvs.add(v)
            depthh[v] = depthh[parent] + dpd

            for u, dpd in d[v]:
                if u in pvs:
                    if depthh[u] != depthh[v] + dpd:
                        return False
                if u in vs:
                    continue
                stack += [(-v, dpd), (u, dpd)]
        else:
            path.pop()

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,ma,mb = map(int,ipt().split())
    mds = [list(map(int,ipt().split())) for i in [0]*n]
    fmt = "0"+str(n)+"b"
    mi = 10**18
    for i in range(2**n):
        li = list(map(int,format(i,fmt)))
        sa = 0
        sb = 0
        cst = 0
        for i,lii in enumerate(li):
            if lii == 1:
                sa += mds[i][0]
                sb += mds[i][1]
                cst += mds[i][2]
        if sa*mb == sb*ma > 0 and mi > cst:
            mi = cst

    if mi == 10**18:
        print(-1)
    else:
        print(mi)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,ma,mb = map(int,ipt().split())
    dp = [[10**18]*(n*10+1) for _ in [0]*(n*10+1)]
    dp[0][0] = 0
    for _ in range(n):
        a,b,c = map(int,ipt().split())
        for i in range(n*10+1-a):
            dpi = dp[n*10-i-a]
            dpni = dp[n*10-i]
            for j in range(n*10+1-b):
                if dpni[n*10-j] > dpi[n*10-j-b]+c:
                    dpni[n*10-j] = dpi[n*10-j-b]+c
    mi = 10**18
    for i in range(1,n*10//max(ma,mb)+1):
        m = dp[ma*i][mb*i]
        if m < mi:
            mi = m
    if mi == 10**18:
        print(-1)
    else:
        print(mi)
    return

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

N = int(input())
g = {i: []for i in range(1, N+1)}    

cache = {}
def dfs(g,start,end):
    stack = [(start, [start], 0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                return length + l
            else:
                stack.append((next, path + [next], length + l))

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

for v in range(1,N+1):
    cache[v] = dfs(g,v,K)

for q in range(Q):
    x, y = map(int,input().split())
    print(cache[x] + cache[y])

### FIXED CODE ###

N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

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

Q, K = map(int,input().split())

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

for q in range(Q):
    x, y = map(int,input().split())
    print(l[x] + l[y])
### BUGGY CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
t = 0
for i in range(n):
    m[i] = int(s[i]) * 10**i % MOD
    t =  (t + m[i]) % MOD
    msum[i+1] = copy.deepcopy(t)

cnt = 0
for i in range(1,n+1):
    cnt += msum[:i].count(msum[i])
print(cnt)

### FIXED CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

ans = 0
for i in range(MOD):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = []

for i in range(n-k+1):
  m = 1
  for j in range(k):
    m *= a[j]
  s.append(m)
  a.pop(0)

for i in range(n-k):
  if s[i] < s[i+1]:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

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

for i in range(n-k):
  if a[i] < a[i + k]:
      print("Yes")
  else:
      print("No")
### BUGGY CODE ###

N = int(input())
S = input()

rlist, glist, blist = [], [], []
for i in range(N):
    if S[i] == "R":
        rlist.append(i)
    elif S[i] == "G":
        glist.append(i)
    else:
        blist.append(i)

rnumber = len(rlist)
gnumber = len(glist)
bnumber = N - rnumber - gnumber
total = rnumber * gnumber * bnumber

overcount = 0
for r in rlist:
    for g in glist:
        for b in blist:
            options = sorted([r,g,b])
            if options[0]+options[2] == 2*options[1]:
                overcount += 1
    
print(total - overcount)

### FIXED CODE ###

N = int(input())
S = input()

x = S.count("R")
y = S.count("G")

total = x*y*(N-x-y)

count = 0
for i in range(N):
    texta = S[i]
    for j in range(i,int((N-1+i)/2)+1):
        if S[j] != texta:
            textb = S[j]
            if S[2*j-i] != texta and S[2*j-i] !=textb:
                count += 1

print(total - count)
### BUGGY CODE ###

n, m, p = map(int, input().split())
edge = []
d = [[] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    edge.append((bi-1,ai-1,-ci+p))
    d[ai-1] += [bi-1]


p0 = [False for i in range(n)]
p0[0] = True
from collections import deque
q = deque([0])
while len(q)>0:
    x = q.popleft()
    for y in d[x]:
        if not p0[y]:
            p0[y] = True
            q.append(y)

dist = [float("inf") for i in range(n)]
dist[n-1] = 0
h = False
for i in range(n):
    updated = False
    for e in edge:
        if dist[e[1]] > dist[e[0]] + e[2] and p0[e[1]] and p0[e[0]]:
            dist[e[1]] = dist[e[0]] + e[2]
            updated = True
    if not updated:
        break
else:
    h = True

if h:
    print(-1)
else:
    print(max(0, -dist[0]))


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


n, m, p = map(int, input().split())
edge0 = []
d = [[] for i in range(n)]
r = [[] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    edge0.append((bi-1,ai-1,-ci+p))
    d[ai-1] += [bi-1]
    r[bi-1] += [ai-1]

p0 = [False for i in range(n)]
p0[0] = True
from collections import deque
q = deque([0])
while len(q)>0:
    x = q.popleft()
    for y in d[x]:
        if not p0[y]:
            p0[y] = True
            q.append(y)
pn = [False for i in range(n)]
pn[n-1] = True
q = deque([n-1])
while len(q) > 0:
    x = q.popleft()
    for y in r[x]:
        if not pn[y] and p0[y]:
            pn[y] = True
            q.append(y)

edge = []
for e in edge0:
    if pn[e[1]] and pn[e[0]]:
        edge += [e]


dist = [float("inf") for i in range(n)]
dist[n-1] = 0
h = False
for i in range(n):
    updated = False
    for e in edge:
        if dist[e[1]] > dist[e[0]] + e[2] and p0[e[1]] and p0[e[0]]:
            dist[e[1]] = dist[e[0]] + e[2]
            updated = True
    if not updated:
        break
else:
    h = True

if h:
    print(-1)
else:
    print(max(0, -dist[0]))
### BUGGY CODE ###

# coding: utf-8
import collections
# Your code her
a = int(input())
b = [int(s) for s in input().split()]
b = sorted(b)
mod = int(1000000)
c = []
d = tuple(c)
e = collections.Counter(b)
X = int(0)
ans = int(0)

for i in range(a):
    if (b[i] in d) is False:
        X = b[i]
        while X <= (mod-b[i]):
            X += b[i]
            c.append(X)
        d = tuple(c)
        X = 0
    else:
        pass

for i in range(a):
    if e.get(b[i]) == 1:
        if (b[i] in d) is False:
            ans += 1

print(ans)

### FIXED CODE ###

import collections
# Your code her
a = int(input())
b = [int(s) for s in input().split()]
b = sorted(b)
mod = int(1000000)
d = {}
e = collections.Counter(b)
X = int(0)
ans = int(0)

for i in range(a):
    if d.get(b[i]) == None:
        if e.get(b[i]) != 1:
            d[b[i]] = 1
        X = b[i]
        while X <= (mod-b[i]):
            X += b[i]
            d[X] = 1
        X = 0
    else:
        pass

for i in range(a):
    if d.get(b[i]) == None:
        ans += 1

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

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
temp = None
for a in range(A + 1):
        for c in range(C + 1):
            if (a + c == K - B):
                if (temp is None):
                    temp = a - c
                else:
                    if (temp < a - c):
                        temp = a - c
print(temp)

### FIXED CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if (A >= K):
    print(K)
else:
    if (B >= (K - A)):
        print(A)
    else:
        print(2*A + B - K)