Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]


def selection(cards):
    for i in range(len(cards)):
        mini = i
        for j in range(i, len(cards)):
            if cards[j][1] < cards[mini][1]:
                mini = j
        cards[i], cards[mini] = cards[mini], cards[i]


def stable_test(orders, crads):
    for order in orders:
        n = -1
        for c in order:
            p = n
            n = cards.index(c)
            if p > n:
                return False
    return True


stdin.readline()
data1 = stdin.readline().split()
data2 = data1[:]
orders = [[c for c in data1 if s.endswith(str(i))] for i in range(1, 10)]
orders = [o for o in orders if len(s) > 1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]


def selection(cards):
    for i in range(len(cards)):
        mini = i
        for j in range(i, len(cards)):
            if cards[j][1] < cards[mini][1]:
                mini = j
        cards[i], cards[mini] = cards[mini], cards[i]


def stable_test(orders, cards):
    for order in orders:
        n = -1
        for c in order:
            p = n
            n = cards.index(c)
            if p > n:
                return False
    return True


stdin.readline()
data1 = stdin.readline().split()
data2 = data1[:]
orders = [[c for c in data1 if c.endswith(str(i))] for i in range(1, 10)]
orders = [o for o in orders if len(c) > 1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')
n,m = map(int,input().split())

if n == 1:
    print(m-2)
else if m == 1:
    print(n-2)
else :
    print((m-2)*(n-2))
    
    

### FIXED CODE ###

n,m = map(int,input().split())

if n == 1 and m != 1:
    print(m-2)
elif m == 1 and n != 1:
    print(n-2)
elif n == 1 and m == 1:
    print(1)
else:
    print((m-2)*(n-2))
(a,b)=(int(),int())
x=a*b
y=(a+b)*2
print(x y)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
N = int(input())
D = 0

for i in range(N + 1):
    D1, D2 = map(int, input().split())
    if D == 3:
        break

    if D1 == D2:
        D += 1

    elif D1 != D2:
        D = 0

if D == 3:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
D = 0

for i in range(N):
    D1, D2 = map(int, input().split())
    if D == 3:
        break

    if D1 == D2:
        D += 1

    elif D1 != D2:
        D = 0

if D == 3:
    print('Yes')
else:
    print('No')
n=int(input())
a=list(map(int, input().split()))
d=[]
for c in range(n):
  b=0
  while a[c]%2==0:
    a[c]=a[c]//2
    b+=1
  d[c].append(b)
print(max(d))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d=[]
for c in range(n):
  b=0
  while a[c]%2==0:
    a[c]=int(a[c]//2)
    b+=1
  d.append(b)
print(min(d))
import bisect
s = input()
t = input()
N = len(s)

next_map = sorted(zip(s*2,range(N*2)))
br = bisect.bisect_right
ans = 0
i = 0
for c in t:
    map_idx = br(next_map,(c,i))
    if map_idx == N*2:
        ans = -2/0
        break
    a,j = next_map[map_idx]
    if a != c :
        ans = -2
        break
    ans += j - i
    i = j%N
ans += 1
print(ans)

### FIXED CODE ###

import bisect
s = input()
t = input()
N = len(s)

next_map = sorted(zip(s*2,range(N*2)))
br = bisect.bisect_right
ans = 0
i = -1
for c in t:
    map_idx = br(next_map,(c,i))
    if map_idx == N*2:
        ans = -1
        break
    a,j = next_map[map_idx]
    if a != c :
        ans = -1
        break
    ans += j - i
    i = j%N
print(ans)
A,B,K = map(int,input().split())
kazu = list(range(A,B+1))
for i in kazu:
	if i < A+K or B-K < i:
		print(i)

### FIXED CODE ###

A,B,K = map(int,input().split())
list_A = list(range(A,min(B,A+K)))
list_B = list(range(max(A,B-K+1),B+1))
list_C = list_A + list_B
set_C = set(list_C)
list_D = sorted(list(set_C))
for i in list_D:
	print(i)
x, n = map(int, input().split())
p = list(map(int, input().split()))

if n == 0:
    print(x)
    exit()

p.sort()
#print(p)
for i in range(n):
    if p[i] == x:
        index = i
        break

right = x + 1
for i in p[index + 1:]:
    #print(i)
    if i != right:
        #print('aaaa')
        #print(right)
        break
    right += 1

left = x - 1
for i in reversed(p[:index]):
    #print(i)
    if i != left:
        #print('bbbb')
        #print(left)
        break
    left -= 1

if x - left <= right - x:
    print(left)
else:
    print(right)

### FIXED CODE ###

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

if n == 0:
    print(x)
    exit()

p.sort()

if x not in p:
    print(x)
    exit()
    
for i in range(len(p)):
    #print(p[i])
    if p[i] == x:
        index = i
        break

right = x + 1
for i in p[index + 1:]:
    if i != right:
        break
    right += 1

left = x - 1
for i in reversed(p[:index]):
    if i != left:
        break
    left -= 1

if x - left <= right - x:
    print(left)
else:
    print(right)
N, M = map(int, input().split())

a = [0 for i in range(N)]
b = [0 for i in range(N)]
c = [0 for i in range(N)]
d = [0 for i in range(N)]

for i in range(N):
    a[i], b[i] = map(int, input().split())
for i in range(M):
    c[i], d[i] = map(int, input().split())
    
for i in range(N):
    closest_ind = -1
    closest_dist = 10000000000
    for j in range(M):
        if closest_dist > abs(a[i] - c[j]) + abs(b[i] - d[j]):
            closest_ind = j
            closest_dist = abs(a[i] - c[j]) + abs(b[i] - d[j])
    print(closest_ind + 1)

### FIXED CODE ###

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

a = [0 for i in range(N)]
b = [0 for i in range(N)]
c = [0 for i in range(M)]
d = [0 for i in range(M)]

for i in range(N):
    a[i], b[i] = map(int, input().split())
for i in range(M):
    c[i], d[i] = map(int, input().split())
    
for i in range(N):
    closest_ind = -1
    closest_dist = 10000000000
    for j in range(M):
        if closest_dist > abs(a[i] - c[j]) + abs(b[i] - d[j]):
            closest_ind = j
            closest_dist = abs(a[i] - c[j]) + abs(b[i] - d[j])
    print(closest_ind + 1)
N = int(input())
aa = map(int, input().split())
if len(set(aa)) != N:
  print('NO')
else:
  print('YES)

### FIXED CODE ###

N = int(input())
aa = map(int, input().split())
if len(set(aa)) != N:
  print('NO')
else:
  print('YES')
X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print("0")
    exit()

n = (-X + 2 * Y) / 3
m = (2 * X - Y) / 3
if n < 0 or m < 0:
    print("0")
else:
    import math
    n, m = int(n), int(m)
    s = 0
    for i in range(2, m + n + 1):
        s += math.log(i)
    for i in range(2, m + 1):
        s -= math.log(i)
    for i in range(2, n + 1):
        s -= math.log(i)
    
    print(int(math.exp(s)) % (10**9 + 7))

### FIXED CODE ###

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print("0")
    exit()

n_right = (-X + 2 * Y) / 3
n_up = (2 * X - Y) / 3
if n_right < 0 or n_up < 0:
    print("0")
    exit()


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10**9 + 7  # 出力の制限
N = 10**6
g1, g2, inverse = [1, 1], [1, 1], [0, 1]

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n_right, n_up = int(n_right), int(n_up)
print(cmb(n_right + n_up, min((n_right, n_up)), mod))
age=input()
if age==1:
  print('Hello World')
 
else:
  A=int(input())
  B=int(input())
  print(A+B)

### FIXED CODE ###

N=int(input())

if N == 1:
    print('Hello World')

if N == 2:
    A=int(input())
    B=int(input())

    print(A+B)
def p(n):
    l = list(range(2,n+1))
    p = 2
    i = 0
    p = l[i]
    while True:
        pl = len(l)
        l = list(filter(lambda n: n%p != 0 or n == p,l))
        i += 1
        p = l[i]
        if pl == len(l):
            break
    return len(l)

from sys import stdin
for i in stdin:
    print(p(int(i)))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
n=int(input())
a=list(map(int,input().split())

cnt=0
l=[]
for i in a:
  p=i//400
  if p<=7:
    l.append(p)
  else:
    cnt+=1

d=len(set(l))
if d==0:
  d+=1
print(d,d+cnt)

### FIXED CODE ###

n=int(input())
a_l=list(map(int,input().split()))
a,b,c,d,e,f,g,h=0,0,0,0,0,0,0,0
cnt=0
for i in a_l:
    if i<400*1:
        a+=1
    elif 400*1<=i<400*2:
        b+=1
    elif 400*2<=i<400*3:
        c+=1
    elif 400*3<=i<400*4:
        d+=1
    elif 400*4<=i<400*5:
        e+=1
    elif 400*5<=i<400*6:
        f+=1
    elif 400*6<=i<400*7:
        g+=1
    elif 400*7<=i<400*8:
        h+=1
    else:
        cnt+=1
ans=0
for i in [a,b,c,d,e,f,g,h]:
    if i!=0:
        ans+=1
if ans!=0:
    print(ans, ans+cnt)
else:
    print(1,cnt)
#!/usr/bin/env python3
ans=0
n,a,b=map(int,input().split())
for i in range(1,n):
    count=0
    for j in str(i):
        count+=j
    if a<=count<=b:
        ans+=1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
ans=0
n,a,b=map(int,input().split())
for i in range(1,n+1):
    count=0
    for j in str(i):
        count+=int(j)
    if a<=count<=b:
        ans+=i
print(ans)
N, X, T = int( input().split() )
if int(N) % int(X) != 0 :
	print( ( int(N) // int(X) + 1) * int(T) )
if int(N) % int(X) == 0 :
	print( (int(N) // int(X) ) * int(T) )


### FIXED CODE ###

N, X, T = map(int, input().split())
if int(N) % int(X) != 0 :
	print( ( int(N) // int(X) + 1) * int(T) )
if int(N) % int(X) == 0 :
	print( (int(N) // int(X) ) * int(T) )
import numpy as np

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

ans = 0
for i in range(N):
    tmp_A = A + A[i]
    tmp_B = np.concatenate([np.zeros(i),np.arange(N-i)])
    C = tmp_B - tmp_A
    ans += np.count_nonzero(C == 0)

print(ans)





### FIXED CODE ###

import numpy as np
from collections import Counter

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.arange(N) + 1

s = A + B
m = B - A

s_ct = Counter(s)
m_ct = Counter(m)

ans = 0
for i in s_ct:
    ans += s_ct[i] * m_ct[i]

print(ans)
from math import floor
a, b = input().split()
print(math.floor(a*b))

### FIXED CODE ###

from math import floor
from decimal import Decimal
a, b = map(Decimal, input().split())
print(floor(a*b))
r=int(input())
print(2*r*math.pi)

### FIXED CODE ###

import math
import numpy as np
r=int(input())
print(np.round(math.pi*2*r,6))
#include<stdio.h>
int main(void){
  int n,sum = 0;
  scanf("%d",&n);
  for(n;n >= 1;n--) sum += n;
  printf(sum);
  return 0;
}

### FIXED CODE ###

n = int(input())
i = 1
sum = 0
for i in range(1,n + 1):
  sum += i
print(sum)
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template #


N, K = mi()
strS = li()
S = [int(i) for i in strS]
S.append(0)
# S.insert(0, 1)
# print(S)

cnt = 0
lis0 = []
if S[0] == 1:
    listart = [0]
else:
    listart = []
liend = []
for i in range(1, N):
    if S[i] == 0:
        cnt += 1
    if S[i] == 0 and S[i + 1] == 1:
        listart.append(i + 1)
        lis0.append(i)
    if S[i-1] == 1 and S[i] == 0:
        liend.append(i-1)
if S[N-1] == 0:
    lis0.append(N)
if S[N-1] == 1:
    liend.append(N-1)
# lis.append(N)
# lis.insert(0, -1)
# print(lis0)
# print(listart)
# print(liend)
ma = max(liend[K - 1] + 1, N - listart[-K])
# print(ma)
if K >= len(lis0):
    print(N)
else:
    for i in range(len(listart) - K):
        ma = max(ma, liend[i+K]-listart[i]+1)
    print(ma)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template #


N, K = mi()
strS = li()
S = [int(i) for i in strS]
S.append(0)
# S.insert(0, 1)
# print(S)

cnt = 0
lis0 = []
if S[0] == 1:
    listart = [0]
    cnt += 1
else:
    listart = []
liend = []
for i in range(1, N):
    # if S[i] == 0:
    #     cnt += 1
    if S[i-1] == 0 and S[i] == 1:
        listart.append(i)
        lis0.append(i)
    if S[i-1] == 1 and S[i] == 0:
        liend.append(i-1)
# if S[N-1] == 0:
#     lis0.append(N)
if S[N-1] == 1:
    liend.append(N - 1)
    cnt += 1
# lis.append(N)
# lis.insert(0, -1)
len0 = len(listart) + 1 - cnt
# print(listart)
# print(liend)
# print(len0)
# print(ma)
if K >= len0:
    print(N)
else:
    ma = max(liend[K - 1] + 1, N - listart[-K])
    for i in range(len(listart) - K):
        ma = max(ma, liend[i+K]-listart[i]+1)
    print(ma)
N = int(input())
arr = list(map(int, input().split()))
result = 1
if 0 in arr:
    result = 0
else:
    for i in a:
        result *= i
        if result > 10**18:
            result = -1
            break
print(result)

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
result = 1
if 0 in arr:
    result = 0
else:
    for i in arr:
        result *= i
        if result > 10**18:
            result = -1
            break
print(result)
A,B = map(int,input().split())
test1 = A+B
test2 = A-B
test3 = A*B
if test1 >= test2 and test1 >= test3:
  print(test1)
  break
if test2 >= test1 and test2 >= test3:
  print(test2)
  break
if test3 >= test1 and test3 >= test2:
  print(test3)
  break
	

### FIXED CODE ###

A,B = map(int,input().split())
test1 = A+B
test2 = A-B
test3 = A*B
if test1 >= test2 and test1 >= test3:
  print(test1)
elif test2 >= test1 and test2 >= test3:
  print(test2)
elif test3 >= test1 and test3 >= test2:
  print(test3)
n,k,x,y = map( int,input().split() )
print(n*x if k>=n else k*x + (n-k)*y)

### FIXED CODE ###

n,k,x,y = [int(input()) for i in range(4)]
print(n*x if k>=n else k*x + (n-k)*y)
from numpy import cumsum
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a=cumsum(a)
b=cumsum(b)

for i in range(n):
    if a[i]>k:
        read=i
        break
if a[n-1]<k:
    read=n
time=a[read-1]
ans=read
start=read-1
if read==n:
    for i in range(m):
        if time+b[i]>k:
            read+=i
            ans=max(ans,read)
            read=-i
        if i==m-1:
            print(n+m)
            exit()
            
for i in range(start+1):
    read-=1
    time-=a[start-i]
    for j in range(m):
        if time+b[j]>k:
            read+=j
            ans=max(ans,read)
            read-=j
            break
        if j==m-1:
            read+=m
            print(max(ans,read))
            exit()
print(ans)

### FIXED CODE ###

from bisect import bisect
from numpy import cumsum
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a=cumsum(a)
b=cumsum(b)

read=bisect(a,k)
time=a[read-1]
ans=read

for i in range(read):
    extra=k-time
    r=bisect(b,extra)
    ans=max(ans,read+r)
    read-=1
    time=a[read-1]
read=bisect(b,k)
ans=max(ans,read)
print(ans)
import sys
input = sys.stdin.readline
num = []
iti = []

for temp in range(5):
    temp2 = input()
    temp3 = int(temp2)
    if temp3 >= 10 and temp2[-2] != "0":
        num.append((int(temp2[0:-2])+1)*10)
    elif temp2[-2] == "0":
        num.append(int(temp2[0:-2])*10)
    else:
        num.append(10)
    if int(temp2[-2]) != 0:
        iti.append(int(temp2[-2]))

print(sum(num)-10+min(iti))

### FIXED CODE ###

import sys
input = sys.stdin.readline
num = []
iti = []

for temp in range(5):
    temp2 = input()
    temp3 = int(temp2)
    if temp3 >= 10 and temp2[-2] != "0":
        num.append((int(temp2[0:-2])+1)*10)
    elif temp2[-2] == "0":
        num.append(int(temp2[0:-2])*10)
    else:
        num.append(10)
    if int(temp2[-2]) != 0:
        iti.append(int(temp2[-2]))

if iti == []:
    last = 10
else:
    last = min(iti)
print(sum(num)-10+last)
n, k = map(int, input().split())

array = list(map(int, input().split()))
array.sort()
total = 0

for i in range(k):
  total+=array[i]
  
print(total)

### FIXED CODE ###

import re

alpha = input()

if(re.compile("[A-Z]").search(alpha)):
    print("A")
else:
    print("a")
from math import atan2,degrees
a,b,x=map(int,input().split())
if 2*x<=b*a*a:
  print(90-degrees(atan2(2*x,a*b*b)))
else:
  print(90-degrees(atan2(a*a*a,2*(a*a*b-x)))


### FIXED CODE ###

from math import atan2,degrees
a,b,x=map(int,input().split())
if 2*x<=b*a*a:
  print(90-degrees(atan2(2*x,a*b*b)))
else:
  print(90-degrees(atan2(a*a*a,2*(a*a*b-x))))
a,b = map(int, input().split())
if a*b > 0:
  print("Positive")
else:
  if any(a,b) > 0:
    print("Zero")
  else:
    print("Negative")

### FIXED CODE ###

a, b = map(int, input().split())
if a > 0 and b > 0:
  print("Positive")
elif a < 0 and  b < 0:
  if (b - a + 1) % 2 == 0:
    print("Positive")
  else:
    print("Negative")
else:
  print("Zero")
#print(x)
y = [int(c) for c in x]
#print(y)
a = y[0]
b = y[1]
c = y[2]
d = y[3]
if a+b+c+d == 7:
  print("a+b+c+d=",a+b+c+d,sep='')
  exit()
if a+b+c-d == 7:
  print("a+b+c-d=",a+b+c-d,sep='')
  exit()
if a+b-c+d == 7:
  print("a+b-c+d=",a+b-c+d,sep='')
  exit()
if a-b+c+d == 7:
  print("a-b+c+d=7")
  exit()
if a-b-c+d == 7:
  print("a-b-c+d=7")
  exit()
if a-b+c-d == 7:
  print("a-b+c-d=7")
  exit()
if a-b-c-d == 7:
  print("a-b-c-d=7")
  exit()
if a+b-c-d == 7:
  print("a+b-c-d=7")
  exit()

### FIXED CODE ###

x = input()
#print(x)
y = [int(c) for c in x]
#print(y)
a = y[0]
b = y[1]
c = y[2]
d = y[3]
if a+b+c+d == 7:
  print(a,"+",b,"+",c,"+",d,"=",a+b+c+d, sep='')
  exit()
if a+b+c-d == 7:
  print(a,"+",b,"+",c,"-",d,"=",a+b+c-d, sep='')
  exit()
if a+b-c+d == 7:
  print(a,"+",b,"-",c,"+",d,"=",a+b-c+d, sep='')
  exit()
if a-b+c+d == 7:
  print(a,"-",b,"+",c,"+",d,"=",a-b+c+d, sep='')
  exit()
if a-b-c+d == 7:
  print(a,"-",b,"-",c,"+",d,"=",a-b-c+d, sep='')
  exit()
if a-b+c-d == 7:
  print(a,"-",b,"+",c,"-",d,"=",a-b+c-d, sep='')
  exit()
if a-b-c-d == 7:
  print(a,"-",b,"-",c,"-",d,"=",a-b-c-d, sep='')
  exit()
if a+b-c-d == 7:
  print(a,"+",b,"-",c,"-",d,"=",a+b-c-d, sep='')
  exit()
S,T = input().split()
a,b = list(map(int,input().split()))
u = input()

if S = u:
    print(a-1,b)
else:
    print(a,b-1)

### FIXED CODE ###

S,T = input().split()
a,b = list(map(int,input().split()))
u = input()
 
if S == u:
    print(a-1,b)
else:
    print(a,b-1)
import io

nim,mike=map(int,input().split())
for i in range(mike-nim+1,b+nim):
    print(i)

### FIXED CODE ###

import io

nim,mike=map(int,input().split())
for i in range(mike-nim+1,mike+nim):
    print(i)
N=int(input())
h=list(map(int,input().split()))
cnt=[]
l=0

for n in range(1,N):
	if h[n-1]>=h[n]:
		l+=1
		if n==N-1:
			cnt.append(l)
			break
		continue
	elif h[n-1]<h[n]:
		cnt.append(l)
		l=0
		continue
print(max(cnt))

### FIXED CODE ###

N=int(input())
h=list(map(int,input().split()))
cnt=[]
l=0

if N==1:
	print(0)
	exit()

for n in range(1,N):
	if h[n-1]>=h[n]:
		l+=1
		if n==N-1:
			cnt.append(l)
			break
		continue
	elif h[n-1]<h[n]:
		cnt.append(l)
		l=0
		continue
print(max(cnt))
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)





### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
V = [i for i in range(N)]
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        if visited[e]:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)
import sys
n = int(input())
a = [*map(int,input().split())]
res = 0
for x in a :
	while (x % 2 == 0) :
		res += 1
		x /= 2
print (res)

### FIXED CODE ###

import sys
n = int(input())
a = input().split(' ')
for i in range(len(a)):
	a[i] = int(a[i])
res = 0
for x in a :
	while (x % 2 == 0) :
		res += 1
		x /= 2
print (res)
import copy

N=int(input())
l=list(map(int, input().split()))  #リスト入力
cp = copy.copy(l)
#c=0

for k in range(N-1):

  if sum(l[:k+1])==0:
    #c=c+1
    if l[k+1]>0:
      l[k+1]=l[k+1]+1
    else:
      l[k+1]=l[k+1]-1

  if sum(l[:k])*sum(l[:k+1])>0:
    
    if sum(l[:k+1])>0:
      l[k]=l[k]-(sum(l[:k+1])-(-1))
      #c=c+abs(sum(l[:k+1])-(-1))
    else:
      l[k]=l[k]+(1-sum(l[:k+1]))
      #c=c+abs(1-sum(l[:k+1]))


if sum(l)==0:
  c=c+1
  l[-1]=l[-1]+1

  
print(sum([abs(l[n]-cp[n]) for n in range(N)]))

### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
import math
import functools
n,x = map(int, input().split())
list_x = list((map(int, input().split())))
list_x.append(x)
list_x.sort()
list_dist = []
for i in range(0,n):
    list_dist.append(list_x[i+1] - list_x[i])
print(functools.reduce(math.gcd,list_dist))


### FIXED CODE ###

def gcd(x,y):
    if x < y:
        (x,y) = (y,x)
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

n,x = map(int, input().split())
list_x = list((map(int, input().split())))
list_x.append(x)
list_x.sort()
list_dist = []
for i in range(0,n):
    list_dist.append(list_x[i+1] - list_x[i])
gcd1 = list_dist[0]
for i in range(1,n):
    gcd1 = gcd(gcd1, list_dist[i])
print(gcd1)