Harryxun/stf_run huggingface dataset:
import bisect


def dfs(v, x, g, used, ans):
    used[v] = True
    res = x[v]
    for e in g[v]:
        if used[e[0]]:
            continue
        r = dfs(e[0], x, g, used, ans)
        if r:
            ans.append(e[1])
        res ^= r
    return res


def main():
    n, m = map(int, input().split())
    ab = []
    ans = []
    g = [[] for _ in range(n+1)]
    used = [False] * (n+1)

    for i in range(n):
        ab.append(list(map(int, input().split())))
    ab = sorted(ab, key=lambda x: x[0])
    al = list(map(lambda x: x[0], ab))
    for i in range(m):
        l, r = map(int, input().split())
        l = bisect.bisect_left(al, l)
        r = bisect.bisect_right(al, r)
        g[l].append((r, i+1))
        g[r].append((l, i+1))

    x = [ab[0][1]]
    for i in range(n-1):
        x.append(ab[i][1] ^ ab[i+1][1])
    x.append(ab[n-1][1])

    for i in range(n+1):
        if used[i]:
            continue
        if dfs(i, x, g, used, ans):
            print(-1)
            return

    ans.sort()
    print(len(ans))
    print(*ans)


main()


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(v, x, g, used, ans):
    used[v] = True
    res = x[v]
    for e in g[v]:
        if used[e[0]]:
            continue
        r = dfs(e[0], x, g, used, ans)
        if r:
            ans.append(e[1])
        res ^= r
    return res


def main():
    n, m = map(int, input().split())
    ab = [[] for _ in range(n)]
    ans = []
    g = [[] for _ in range(n+1)]
    used = [False] * (n+1)

    for i in range(n):
        ab[i] = list(map(int, input().split()))
    ab = sorted(ab, key=lambda x: x[0])
    al = list(map(lambda x: x[0], ab))
    for i in range(m):
        l, r = map(int, input().split())
        l = bisect.bisect_left(al, l)
        r = bisect.bisect_right(al, r)
        g[l].append((r, i+1))
        g[r].append((l, i+1))

    x = [0] * (n+1)
    x[0] = ab[0][1]
    for i in range(n-1):
        x[i+1] = ab[i][1] ^ ab[i+1][1]
    x[n] = ab[n-1][1]

    for i in range(n+1):
        if used[i]:
            continue
        if dfs(i, x, g, used, ans):
            print(-1)
            return

    ans.sort()
    print(len(ans))
    print(*ans)


main()
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<vector<int> > Matrix;

const int INF = 100000000;
Matrix d; // グラフの距離を格納した2次元配列（隣接行列）
Matrix D; // d[u][v]は辺e=(u,v)のコスト（辺が存在しない場合はINF、ただしd[i][i]=0）

void warshall_floyd(int n) { // nは頂点数
  for (int i = 0; i < n; i++)      // 経由する頂点
    for (int j = 0; j < n; j++)    // 開始頂点
      for (int k = 0; k < n; k++)  // 終端
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}




int main() {
  int n;
  cin >> n;

  d = Matrix(n, vector<int>(n, INF));
  D = Matrix(n, vector<int>(n, INF));
  for (int i = 0; i < n; i++) d[i][i] = 0;
  
  int tmp;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin>>tmp;
      d[i][j] = tmp;
      d[j][i] = tmp;
      D[i][j] = tmp;
      D[j][i] = tmp;
    }
  }
  
  warshall_floyd(n);
  
  int ans=100000000;
  tmp=0;
  
  if (D!=d){ cout<< -1 <<endl;
  }else{
      cout<<"1"<<endl;
      
      
  }
}


### FIXED CODE ###

n=int(input())
a=int(input())
print(n**2-a)
def main():
    n = int(input())
    numbers = [int(input()) for i in range(n)]
    count = shellSort(numbers, n)

    print(count)
    [print(i) for i in numbers]

def shellSort(numbers, n):
    count = 0
    m = 1
    g = []
    while m <= n :
        g.append(m)
        m = 3 * m + 1

    for i in range(len(g), -1, -1):
        count += insertionSort(numbers, n, g[i])

    print(len(g))
    print(' '.join(map(str, g)))

    return count

def insertionSort(numbers, n, h):
    count = 0
    for i in range(h, n, 1):
        v = numbers[i]
        j = i - h
        while (j >= 0) & (numbers[j] > v):
            numbers[j + h] = numbers[j]
            j -= h
            count += 1

        numbers[j + h] = v

    return count

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n = int(input())
    numbers = [int(input()) for i in range(n)]
    count = shellSort(numbers, n)

    print(count)
    [print(i) for i in numbers]

def shellSort(numbers, n):
    count = 0
    m = 1
    g = []
    while m <= n :
        g.append(m)
        m = 3 * m + 1
    g.reverse()
    for h in g:
        count += insertionSort(numbers, n, h)

    print(len(g))
    print(' '.join(map(str, g)))

    return count

def insertionSort(numbers, n, h):
    count = 0
    for i in range(h, n, 1):
        v = numbers[i]
        j = i - h
        while (j >= 0) & (numbers[j] > v):
            numbers[j + h] = numbers[j]
            j -= h
            count += 1

        numbers[j + h] = v

    return count

if __name__ == '__main__':
    main()
H, W, N, *L = map(int, open('0').read().split())
dic = {}
for a, b in zip(*[iter(L)]*2):
  for i in range(a-2,a+1):
    for j in range(b-2,b+1):
      if 0<i and i+2<=H and 0<j and j+2<=W:
        dic[i*W+j] = dic.get(i*W+j,0)+1
ans = [0]*10
ans[0] = (W-2)*(H-2)
for k in dic.keys():
  ans[dic[k]] += 1
  ans[0] -= 1
print('\n'.join(map(str,ans)))

### FIXED CODE ###

from collections import defaultdict
H, W, N, *L = map(int, open(0).read().split())
dic = defaultdict(int)
for a, b in zip(*[iter(L)]*2):
  for i in range(a-2,a+1):
    for j in range(b-2,b+1):
      if 0<i and i+2<=H and 0<j and j+2<=W:
        dic[(i,j)] += 1
ans = [0]*10
ans[0] = (W-2)*(H-2)
for k in dic.keys():
  ans[dic[k]] += 1
  ans[0] -= 1
print(*ans,sep='\n')
n=int(input())
a=list(map(int,input().split()))
a.sort()
if sum(a)==0:
    print('Yes')
    exit()
x=[]
x[0] = a.count(a[0])
x[1] = a.count(a[n//2])
x[2] = a.count(a[-1])
x.sort()

if x[0] == x[1] == x[2] == n//3 or (a[0] == 0 and x[0]==n//3 and x[1]==x[2]==2*n//3):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
if sum(a)==0:
    print('Yes')
    exit()
x=[0]*3
x[0] = a.count(a[0])
x[1] = a.count(a[n//2])
x[2] = a.count(a[-1])
x.sort()

if a[0]^a[n//2] == a[-1] and x[0] == x[1] == x[2] == n//3:
    print('Yes')
elif a[0] == 0 and x[0] == n//3 and x[1] == x[2] == n*2//3:
    print('Yes')
else:
    print('No')
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[False] * W for _ in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i][j] = True
      queue.append((i,j))
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if i > 0 and not dist_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if i < H-1 and not dist_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if j > 0 and not dist_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if j < W-1 and not dist_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
S_list = [input() for i in range(2)]
S_list_1 = S_list[1].split()

for i in S_list_1:   
    if int(i) % 2 == 0 :
        if i % 3 !=0 and i % 5 !=0 :
            result="DENIED"
            break
    else:
        result="APPROVED"        
print(result)

### FIXED CODE ###

S_list = [input() for i in range(2)]
S_list_1 = list(map(int,S_list[1].split()))

for i in S_list_1:   
    if i % 2 == 0 :
        if i % 3 !=0 and i % 5 !=0 :
            result="DENIED"
            break
    else:
        result="APPROVED"        
print(result)
MOD=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))

a.sort(reverse=True)


from scipy.misc import comb


def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod
  
  
c=[]
for i in range(1,n+1):
  c.append(mod_combination(n-i,k-1,MOD))
lc=len(c)
#print(c,a)
sum=0
for i in range(lc):
  sum+=c[i]*(a[i]-a[-i-1])%MOD
  
print(sum%MOD)


### FIXED CODE ###

MOD=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))

a.sort(reverse=True)


fact = [1]
fact_inv = [1]
mod=10**9+7
for i in range(10**5+1):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

  
c=[]
for i in range(1,n-k+1+1):
  c.append(mod_comb_k(n-i,k-1,MOD))
lc=len(c)
#print(c,a)
sum=0
for i in range(lc):
  sum+=c[i]*(a[i]-a[-i-1])%MOD
  
print(sum%MOD)
a,b=map(int,input().split())
s=[2**i for i in range(38)]
d=[0]*38
i=1
if ((b+1)//2-a//2)%2==1:
    d[0]+=1
while i<39:
    if s[i]>b:
        break
    elif s[i]>a: 
        a=s[i]
    p,q=a%s[i],a//s[i]
    o,t=b%s[i],b//s[i]
    if q==t:
        if q%2==1:
            if (b-a+1)%2==1:
                d[i]=1
    else:
        h=0
        if q%2==1:
            h+=(q+1)*s[i]-a  
        if t%2==1:
            h+=b-t*s[i]+1
        if h%2==1:
            d[i]=1
    i+=1
ans=0
for i in range(38):
    ans+=d[i]*s[i]
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
s=[2**i for i in range(42)]
d=[0]*42
i=1
if ((b+1)//2-a//2)%2==1:
    d[0]+=1
while i<42:
    if s[i]>b:
        break
    elif s[i]>a: 
        a=s[i]
    p,q=a%s[i],a//s[i]
    o,t=b%s[i],b//s[i]
    if q==t:
        if q%2==1:
            if (b-a+1)%2==1:
                d[i]=1
    else:
        h=0
        if q%2==1:
            h+=(q+1)*s[i]-a  
        if t%2==1:
            h+=b-t*s[i]+1
        if h%2==1:
            d[i]=1
    i+=1
ans=0
for i in range(42):
    ans+=d[i]*s[i]
print(ans)
N=input()
if s[-1]==3:
    print ("bon")
elif s[-1]==0 or s[-1]==8 or s[-1]==6 or s[-1]==1:
    print("pon")
else:
    print("hon")   

### FIXED CODE ###

N=input()
if N[-1]=="3":
    print ("bon")
elif N[-1]=="0" or N[-1]=="8" or N[-1]=="6" or N[-1]=="1":
    print("pon")
else:
    print("hon")
ipt1 = [int(i) for i in input().split()]
a = [int(i) for i  in input().split()]
n = ipt1[0]
m = ipt1[1]
x = ipt1[2]
cost_0 = 0
cost_n = 0
for i in range(m):
    if a[i] < x:
        cost_0 += 1
    else:
        cost_n += 1

print(int(min(cost_0, cost_n)))


### FIXED CODE ###

ipt = [int(i) for i in input().split()]
a = ipt[0]
b = ipt[1]
x = ipt[2]

if a <= x and x <= a+b:
    print("YES")
else:
    print("NO")
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    K = int(input())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    # N = 5
    # K g= 3
    # h = [10,15,11,14,12]
    N = 5
    K = 3
    h = [5,7,5,7,7]

  h.sort()
  for i in range(0,len(h)-2):
    if i == 0:
      ans = (h[2] - h[1]) + (h[1] - h[0])
    else:
      tmp = (h[i+2] - h[i+1]) + (h[i+1] - h[i])
      if ans > tmp:
        ans = tmp
  
  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    N = 5
    K = 3
    h = [10,15,11,14,12]
    # N = 5
    # K = 3
    # h = [5,7,5,7,7]

  h.sort()  

  ans = (h[K-1] - h[0])
  
  max_i = len(h)-K+1
  for i in range(1,max_i):
    tmp = (h[i+K-1] - h[i])
    if ans > tmp:
      ans = tmp
    if ans == 0:
      print(ans)
      sys.exit()
  
  print(ans)

main()
import numpy as np

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

l = [int(i) for i in input().split()]
l.sort()
d = [0 for i in range(m - 1)]
for i in range(m-1):
    d[i] = l[i+1] - l[i]
d = np.array(d)
dl = d.argsort()[::-1]
count = 0
if n == 1 or m == 1:
    print(l[-1]-l[0])
else:
    for i in range(n):
        if i == 0:
            count += l[dl[i]] - l[0]
            index = dl[i]
        elif i == n - 1:
            count += l[-1] - l[index+1]
        else:
            count += l[dl[i]] - l[index+1]
            index = dl[i]
print(count)


### FIXED CODE ###

import numpy as np

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

l = [int(i) for i in input().split()]
l.sort()
if n == 1 or m == 1:
    print(l[-1]-l[0])
elif n > m:
    print(0)
else:
    d = [0 for i in range(m - 1)]
    for i in range(m-1):
        d[i] = l[i+1] - l[i]
    d = np.array(d)
    dl = d.argsort()[::-1]
    count = 0
    for i in range(n):
        if i == 0:
            count += l[dl[i]] - l[0]
            index = dl[i]
        elif i == n - 1:
            count += l[-1] - l[index+1]
        else:
            count += l[dl[i]] - l[index+1]
            index = dl[i]
    print(count)
# 2019-11-21 01:26:03(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 

def is_palindrome_in(s):
    s = s.replace('x', '')
    if s == ''.join(reversed(s)):
        return True
    else:
        return False

def main():
    s = sys.stdin.readline().rstrip()
    
    if not is_palindrome_in(s):
        print(-1)
        sys.exit()

    s = collections.deque(s)
    count = 0
    i, j = 0, 0
    while i < len(s) - 1 - j:
        if s[i] == 'x':
            if s[-1-j] != 'x':
                s.insert(len(s)-j, 'x')
                count += 1
        elif s[-1-j] == 'x':
            s.insert(i, 'x')
            count += 1
        
        i += 1
        j += 1

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-21 01:26:03(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 

def is_palindrome_in(s):
    s = s.replace('x', '')
    if list(s) == list(reversed(s)):
        return True
    return False

def main():
    s = sys.stdin.readline().rstrip()
    
    if not is_palindrome_in(s):
        print(-1)
        sys.exit()
    
    s = collections.deque(s)
    
    count = 0
    while len(s) > 1:
        if s[0] == 'x':
            if s[-1] == 'x':
                s.popleft(); s.pop()
            else:
                s.popleft()
                count += 1
        else:
            if s[-1] != 'x':
                s.popleft(); s.pop()
            else:
                s.pop()
                count += 1

    print(count)

if __name__ == "__main__":
    main()
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
r = 0
p = 0
seen = {0}
for i in range(k):
    x = a[p] - 1
    if x in seen:
        p = 0
        seen = {0}
        for j in range((k - 1) % r):
            p = a[p] - 1
            ans = p + 1
        print(ans)
        exit()
    p = x
    seen.add(p)
    r = i + 1
    ans = p + 1
print(ans)


### FIXED CODE ###

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

b = 0
r = k + 1
seen = [-1] * n
seen[0] = 0
p = 1
for i in range(k):
    p = a[p - 1]
    if seen[p - 1] != -1:
        b = seen[p - 1]
        r = i + 1 - b
        for j in range((k - b) % r):
            p = a[p - 1]
        print(p)
        exit()
    seen[p - 1] = i + 1
else:
    print(p)
def main():
  n=int(input())
  l=list(map(int,input().split()))
  k=[0]*n
  for i in range(1,n+1):
    k[l[i]-1]=str(i)
  print(" ".join(k))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  n=int(input())
  l=list(map(int,input().split()))
  k=[0]*n
  for i in range(1,n+1):
    k[l[i-1]-1]=str(i)
  print(" ".join(k))


if __name__ == '__main__':
    main()
s=str(input())

for i in range(s):
    if i%2==0 and s[i]=="R":
        print("No")
    elif i%2==1 and s[i]=="L":
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

import sys

s=str(input())

for i in range(len(s)):
    if i%2==0 and s[i]=="L":
        print("No")
        sys.exit(0)
    elif i%2==1 and s[i]=="R":
        print("No")
        sys.exit(0)

print("Yes")
N = input()
h = map(int,input().split())
h = list(h)

dp = [99999999 for i in range(100)]
dp[0]=0

for i in range(int(N)):
    for j in range(i+1,i+2)+1:
        if j<int(N) :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

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

### FIXED CODE ###

import sys
n =int(input())
h = map(int,input().split())
h = list(h)

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
    for j in range(i+1,i+2+1):
        if j<n :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

print(dp[n-1])
def solve(string):
    n, *v = map(int, string.split())
    v = sorted(v, reverse=True)
    return str(sum(_v / 2**i for i, _v in enumerate(v[:-1], start=1)) + v[-1] / 2**(n - 1))


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

def solve(string):
    n, *v = map(int, string.split())
    v = sorted(v, reverse=True)
    return str(sum(_v / 2**i for i, _v in enumerate(v[:-1], start=1)) + v[-1] / 2**(n - 1))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
import math
def lcm(a, b):
    return a*b // math.gcd(a, b)

import sys
input = sys.stdin.readline
N = int(input())
print(lcm(2, N))

### FIXED CODE ###

from fractions import gcd
#最小公倍数
def lcm(a, b):
    return a*b // gcd(a, b)

import sys
input = sys.stdin.readline
N = int(input())
print(lcm(2, N))
n = int(input())
A = input().split()

if len(A) % 2:
  B = [A[-i][::-1] for i in range(1, len(A)-1, 2)] + A[1::2]
else:
  B = [A[-i][::-1] for i in range(1, len(A), 2)] + A[::2]
  b = "".join(B)
print(*b)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if n >= 2:
  for i in range(n, 0, -2):
    print(A[i-1], end=" ")
  for i in range(n % 2, n - 2, 2):
    print(A[i], end=" ")
  print(A[n-2])
if n == 1:
  print(*A)
# ABC148B

n = int(input)
s = input()
t = input()
print(''.join([i+j for i, j in zip(s, t)]))


### FIXED CODE ###

# ABC148B

n = int(input())
s, t = input().split()
print(''.join([i+j for i, j in zip(s, t)]))
n = int(input()) # the num of monster
 
ls = list(map(int, input().split()))
n = len(ls)
ans = math.gcd(ls[0], ls[1])

for i in range(n):
    ans = math.gcd(ans, ls[i])
    
print(ans)

### FIXED CODE ###

n = int(input()) # the num of monster
 
ls = list(map(int, input().split()))
n = len(ls)

def gcd(a,b):
  while b != 0:
    a,b = b, a % b
  return a

ans = gcd(ls[0], ls[1])
 
for i in range(n):
    ans = gcd(ans, ls[i])
    
print(ans)
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
A = list(map(int, input().split()))
A = [0] + A

ans = 0
for i in range(1, len(A)+1):
    if i % 2 == 1 and A[i] % 2 == 1:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [0] + A

ans = 0
for i in range(1, len(A)):
    if i % 2 == 1 and A[i] % 2 == 1:
        ans += 1
print(ans)
N = int.input()
oturi = N%1000
print(oturi)

### FIXED CODE ###

N = int(input())
if N % 1000 == 0:
  print(0)
else:
  print(1000-(N%1000))
import math
N,M= list(map(int,input().split()))
S =input()
T=input()


L = N*M//math.gcd(N,M)

d = dict()

for i in range(N):
    index = 1+(L//N)*i
    d[index] = S[i]

for j in range(M):
    index = (1+(L//M)*j)
    if index in d:
        if d[index]!=T[j]:
            print(-1)
            exit()
print(L)





### FIXED CODE ###

import math

N, M = list(map(int, input().split()))
S = input()
T = input()
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

L = N * M // gcd(N, M)

d = dict()

for i in range(N):
    index = 1 + (L // N) * i
    d[index] = S[i]

for j in range(M):
    index = (1 + (L // M) * j)
    if index in d:
        if d[index] != T[j]:
            print(-1)
            exit()
print(L)