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

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)
def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

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

hit = 0
throw = []
for i in range(N):
    h, t = map(int, input().split())
    if h > hit:
        hit = h
    throw.append(t)

throw.sort()


ans = 0
for t in throw[::-1]:
    if t < hit:
        break
    else:
        ans += 1
        HP -= t
        if HP <= 0:
            break

while HP > 0:
    ans += 1
    HP -= hit
print(ans)

### FIXED CODE ###

import math

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

hit = 0
throw = []
for i in range(N):
    h, t = map(int, input().split())
    if h > hit:
        hit = h
    throw.append(t)

throw.sort()

ans = 0
for t in throw[::-1]:
    if t < hit:
        break
    else:
        ans += 1
        HP -= t
        if HP <= 0:
            break
if HP > 0:
    ans += HP // hit
    if HP % hit != 0:
        ans += 1

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

N = int(input())
S = [int(x) for x in list(input())]
total = []
for x in range(N-2):
  for y in range(x+1,N-1):
    for z in range(y+1,N):
      total.append(S[x]*100+S[y]*10+S[z])
print(len(set(total)))

### FIXED CODE ###

N = int(input())
S = [int(x) for x in list(input())]
total = 0
for a in range(1000):
  tmp = [a//100,a//10%10,a%10]
  i = 0
  for x in range(N):
    if tmp[i] == S[x]:
      i+=1
    if i==3:
      total+=1
      break
print(total)
### BUGGY CODE ###

#!/usr/bin/env python
import sys 
import copy
input = sys.stdin.readline

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

for i in range(n):
    xx = copy.deepcopy(x)
    xx.pop(i)
    xx = sorted(xx)
    print(xx[(n-1)//2])


### FIXED CODE ###

#!/usr/bin/env python
import sys 
import copy
input = sys.stdin.readline

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

l = xx[(n-1)//2]
r = xx[n//2]
mid = (l+r)/2

for i in range(n):
    if x[i] >= mid:
        print(l)
    else:
        print(r)
### BUGGY CODE ###

# coding: utf-8

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

ans = 1
for i in range(N):
    ans *= A[i]

if ans > 10**18:
    ans = -1

print(ans)

### FIXED CODE ###

# coding: utf-8

N = int(input())
A = sorted(list(map(int,input().split())))
if A[0] == 0:
    ans = 0
else:
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            ans = -1
            break

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

import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for ab in AB: # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])
### BUGGY CODE ###

N, M = map(int, input().split())
# P_S = [ input().split() for _ in range(M)]

AC = 0
WA = 0
WA_dict = {i: 0 for i in range(1, N+1)}
exc = []

for _ in range(M):
    p, s = input().split()
    if p in exc:
        continue
    elif s=='WA':
        WA_dict[int(p)] += 1
    else:
        AC += 1
        WA += WA_dict[int(p)]
        exc.append(p)

print(AC, WA)



### FIXED CODE ###

N, M = map(int, input().split())
# P_S = [ input().split() for _ in range(M)]

AC = 0
WA = 0
WA_dict = {i: 0 for i in range(1, N+1)}
AC_dict = {i: 0 for i in range(1, N+1)}

for _ in range(M):
    p, s = input().split()
    if AC_dict[int(p)]==1:
        continue
    elif s=='WA':
        WA_dict[int(p)] += 1
    else:
        AC += 1
        AC_dict[int(p)] = 1
        WA += WA_dict[int(p)]
print(AC, WA)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans*=a[i]
if ans > pow(10,18):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for i in range(n):
    ans*=a[i]
    if ans > pow(10,18) or ans==0:
        break
if ans > pow(10,18):
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

A.sort()
F.sort(reverse=True)
AxF = [A[i]*F[i] for i in range(N)]
AxFmax = max(AxF)

def is_possible(x):
    _sum = 0
    for i in range(N):
        _sum += max(0, A[i] - x//F[i])
    #print(x,_sum,K)
    return _sum <= K

left = 0
right = AxFmax

while(left != right):
    x = (left+right)//2
    if is_possible(x):
        right = x
    else:
        left = x+1
    #print('main', left, right, x)
            
print(left)


### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

A.sort()
F.sort(reverse=True)
AxF = [A[i]*F[i] for i in range(N)]
AxFmax = max(AxF)

def is_possible(x):
    _sum = 0
    for i in range(N):
        _sum += max(0, A[i] - x//F[i])
    #print(x,_sum,K)
    return _sum <= K

left = 0
right = AxFmax

while(left != right):
    x = (left+right)//2
    if is_possible(x):
        right = x
    else:
        left = x+1
    #print('main', left, right, x)
            
print(left)
### BUGGY CODE ###

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

for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
        if ans == 0:
            break
print(a)


### FIXED CODE ###

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

if(R-L > 2019):
    R = L+2019
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
print(a)
### BUGGY CODE ###

S = input()
l = len(S)
c = l

while True:
    S = S.replace('01', '')
    S = S.replace('10', '')

    if(len(S) == c):
        break

    c = len(S)

print(l - len(S))


### FIXED CODE ###

import numpy as np

S = np.array(list(map(int, input())))

n0 = (S == 0).sum()
n1 = (S == 1).sum()

print(min(n0, n1) * 2)
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect_left
n = int(input())
s = input()
c = 0
f = defaultdict(list)
for i in range(n):
	f[s[i]].append(i)
for i in range(n):
	for j in range(i+1, n):
		if  s[i] != s[j]:
			for k in f:
				if k != s[i] and k != s[j]:
					t = bisect_left(f[k], j+1)
					t1 = bisect_left(f[k][t:], 2*j - i)
					try:
						if f[k][t:][t1] == 2*j - i:
							c += len(f[k][t:]) - 1	
						else:
							c += len(f[k][t:])
					except:
						c += len(f[k][t:])
print(c)

### FIXED CODE ###

n = int(input())
s = input()
# B_map = set()
R, G, B = 0, 0, 0
for i in range(n):
	if s[i] == 'R':
		R += 1
	elif s[i] == 'G':
		G += 1
	else:
		B += 1

res = R * G * B

for i in range(n):
	for j in range(i+1, n):
		temp = 2*j - i
		if temp < n and s[i] != s[j] and s[j] != s[temp] and s[temp] != s[i]:
			res -= 1
print(res)
### BUGGY CODE ###

import numpy as np
n,a=map(int,input().split())
X=[int(i) for i in input().split()]
DP=np.zeros((n+1,n+1,50*n+1),dtype=int)
DP[0][0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    for s in range(50*j+1):
      DP[i][j][s]=DP[i-1][j][s]+DP[i-1][j-1][s-X[i-1]]
ans=0
for j in range(1,n+1):
  ans+=DP[n][j][j*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
X=[int(i) for i in input().split()]
DP=[[[0 for i in range(50*n+1)] for i in range(n+1)] for i in range(n+1)]
DP[0][0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    for s in range(50*j+1):
      DP[i][j][s]=DP[i-1][j][s]+DP[i-1][j-1][s-X[i-1]]
ans=0
for j in range(1,n+1):
  ans+=DP[n][j][j*a]
print(ans)
### BUGGY CODE ###

import sys
BIG = 10**9 + 7
def sumpp(n,a):
    acc = 0
    for i in range(n-1):
        acc += a[i] * sum(a[i+1:])
    return acc % BIG
input = sys.stdin.readline
if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    print(sumpp(n,a))


### FIXED CODE ###

import sys
input = sys.stdin.readline
BIG = 10**9 + 7

def sumpp(n,a):
    acc = 0
    tmp = 0
    sumv = sum(a)
    for i in range(n):
        tmp += a[i]
        acc += a[i] * (sumv - tmp)
    return acc % BIG

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    print(sumpp(n,a))
### BUGGY CODE ###

n = int(input())
uvw = []
for i in range(n-1):
    uvw.append(list(map(int, input().split(' '))))
result = [0]*(n+1)
result[uvw[0][1]] = uvw[0][2]
s = uvw[0][0]
del uvw[0]
n_visit = []
horyuu = []
count = n-2
while count > 0:
    for i in range(len(uvw)):
        if uvw[i][1] != s and uvw[i][0] != s:
            if result[uvw[i][0]] == 0 and result[uvw[i][1]] != 0:
                result[uvw[i][0]] =  result[uvw[i][1]] + uvw[i][2]
                count -= 1
            elif result[uvw[i][0]] != 0 and result[uvw[i][1]] == 0:
                result[uvw[i][1]] =  result[uvw[i][0]] + uvw[i][2]
                count -= 1
        else:
            if uvw[i][1] != s and uvw[i][0] == s:
                result[uvw[i][1]] = uvw[i][2]
                count -= 1
            elif uvw[i][0] != s and uvw[i][1] == s:
                result[uvw[i][0]] = uvw[i][2]
                count -= 1
            else:
                horyuu.append(uvw[i])
    uvw = horyuu
    horyuu = []

for i in range(1,n+1):
    if result[i]%2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    friends[u].append([v, w])
    friends[v].append([u, w])

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)
max_a = a[-1] 

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0 or inv > max_a:
            continue
        if item == inv:
            if ca[inv] > 1:
                ans += 1 
                ca[inv] -= 2
                break
        else:
            if ca[inv] > 0:
                ans += 1 
                ca[inv] -=1
                ca[item] -=1
                break
print(ans)
### BUGGY CODE ###

import math
from functools import lru_cache


def resolve():
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = map(int, input().split())

    A = sorted(A)
    B = A[::-1]

    @lru_cache(maxsize=None)
    def permutations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    sum = 0
    for i in range(K-1, N):
        sum += permutations_count(i, K-1) * A[i] % MOD
        sum -= permutations_count(i, K-1) * B[i] % MOD
        #print(sum)

    print(sum % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count____(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    def combinations_count_(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    def combinations_count(n, r, mod=10**9+7):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod
    
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


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

# input
N, Q = map(int, input().split())
S = input()

substrs = []
s_append = substrs.append
for i in range(Q):
    l, r = map(int, input().split())
    s_append(S[l - 1:r])

# check
for substr in substrs:
    substr_len = len(substr)
    AC_cnt = substr.replace("AC", "*").count("*")

    print(AC_cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

a = [0] * N
c = [False] * N
for i in range(1, N):
    if S[i - 1:i + 1] == "AC":
        a[i] = a[i - 1] + 1
        c[i] = True
    else:
        a[i] = a[i - 1]

for i in range(Q):
    l, r = map(int, input().split())
    if l - 1 == 0:
        print(a[r - 1])
    elif c[l - 1] is True:
        print(a[r - 1] - a[l - 1])
    else:
        print(a[r - 1] - a[l - 1])
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(N-K+1):
    ans = max(ans,sum(p[i:i+K]))
print(ans/2+0.5*K)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans = sum(p[:K])
tmp = ans
for i in range(K,N):
    tmp += p[i]-p[i-K]
    ans = max(ans,tmp)
print((ans+K)/2)
### BUGGY CODE ###

N,x=map(int,input().split())
A=list(map(int,input().split()))
B=[[0 for k in range(N)]for k in range(x+1)]
for k in range(x+1):
    for n in range(N):
        if n%2==0:
            B[k][n]=x-k
        else:
            B[k][n]=k
#print(B)

ans=[0 for k in range(x+1)]
for k in range(x+1):
    for n in range(N):
        if A[n]-B[k][n]>0:
            ans[k] +=A[n]-B[k][n]

print(min(ans))

### FIXED CODE ###

N,x=map(int,input().split())
A=list(map(int,input().split()))
import copy
C=copy.copy(A)
B=[0 for k in range(N-1)]
for k in range(N-1):
    B[k]=A[k]+A[k+1]
#print(B)
for k in range(N-1):
    if B[k]-x>0:
        if B[k]-x>A[k+1]:
            A[k]=x
            A[k+1]=0
        else:
            A[k+1]=A[k+1]-B[k]+x
        if k!=N-2:
            B[k+1]=A[k+1]+A[k+2]
#print(A)
ans=0
for k in range(N):
    ans+=C[k]-A[k]
print(ans)
### BUGGY CODE ###

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

cnt = 1

for i in range(n):
    cnt = cnt * a[i]

if cnt > 10**18:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

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

    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return

    print(prod)


main()
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    INF = 10 ** 9 + 10

    N, M, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())

    memo = [[-1] * (len(B) + 1) for _ in range(len(A) + 1)]

    def rec(t, ai, bi):
        if t > K: return -INF
        if ~memo[ai][bi]: return memo[ai][bi]

        ac, bc = INF, INF
        if ai < len(A): ac = A[ai]
        if bi < len(B): bc = B[bi]

        ret = max(
            0,
            rec(t + ac, ai + 1, bi) + 1,
            rec(t + bc, ai, bi + 1) + 1
        )

        memo[ai][bi] = ret
        return ret

    print(rec(0, 0, 0))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    *P, = accumulate(A)
    *Q, = accumulate(B)

    ans = 0
    j = len(Q) - 1
    for i, x in enumerate(P):
        while j > 0 and x + Q[j] > K:
            j -= 1
        if x + Q[j] <= K:
            ans = max(ans, i + j)
    print(ans)


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

import numpy as np
s = str(input())
s_list = np.array([int(list(s)[i]) for i in range(len(s))])

if len(s_list) % 2 == 0:
    s01 = np.array([0,1]*(len(s_list)//2))
    s10 = np.array([1,0]*(len(s_list)//2))
else:
    s01 = np.array([0,1]*(len(s_list)//2))
    s01 = np.append(s01, 0)
    s10 = np.array([1,0]*(len(s_list)//2))
    s10 = np.append(s10, 1)

ans = min(np.sum(s_list == s01), np.sum(s_list == s10))
print(ans)

### FIXED CODE ###

s = str(input())
ans1 = s[::2].count('0') + s[1::2].count('1')
ans2 = s[::2].count('1') + s[1::2].count('0')
print(min(ans1, ans2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vset = set()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = []
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vset:
            return 0 
        else:
            vset.add((prev, n))
    else:
        if (n, prev) in vset:
            return 0 
        else:
            vset.add((n, prev))
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0

dfs(-1, max(0, n - 2))
print("\n".join([str(f) + " " + str(t) for f, t in ans]))

### FIXED CODE ###

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

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

n = int(input())

R = []

for i in range(0,n):
    R.insert(i,int(input()))

MAX = R[1] - R[0]
for r in range(2,n):
    if(MAX < R[r] - min(R[:r])):
        MAX = R[r] - min(R[:r])
print(MAX)

### FIXED CODE ###

n = int(input())

R = []

for i in range(0,n):
    R.insert(i, int(input()))

maxV = -2000000000  # ????°??????????????????????????¨????????????????
minV = R[0]

for r in range(1, n):
    maxV = max(maxV, R[r] - minV)
    minV = min(minV, R[r])

print(maxV)