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

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(Q):
    m = -1
    spam = int(input())
    for n in C:
        ham =n%spam 
        m =  max(m,ham) 
    print(m)

### FIXED CODE ###

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m, amr) 
        tmp = n_v-m-1
        if tmp <= 0: break
        n_v = t2[tmp]

    print(m)
### BUGGY CODE ###

# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
N,M,K = map(int,input().split())

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

sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=sum(A[:i])
        count += i

    for j in range(M+1):
        if j == 0:
            sum_time += 0
        else:
            sum_time += sum(B[:j])
            count += j
        if sum_time > K:
            break
        max_count = max(max_count,count)
        sum_time -= sum(B[:j])
        count -= j

print(max_count)

### FIXED CODE ###

# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
suma = 0
sumb = 0

As = [0]*N
for i,a in enumerate(A):
    suma += A[i]
    As[i] = suma

Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=As[i-1]
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)
### BUGGY CODE ###

#!/usr/bin/env python3
import os


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
  print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

maximum = max(a)
ans = [maximum]*n
if a.count(maximum) ==1:
    maximum_index = a.index(maximum)
    ans[maximum_index] = max(
        a[:maximum_index]+a[maximum_index+1:]
    )
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # j番目の足場からi番目の足場に飛ぶ
    min_cost = float("inf")
    for j in range(max(i - K, 0), i):

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])
        min_cost = min(cost, min_cost)

    # 最適コストで更新
    dp_list[i] = min_cost

ans = dp_list[-1]
print(ans)


### FIXED CODE ###

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # j番目の足場からi番目の足場に飛ぶ

    for j in range(max(i - K, 0), i + 1):

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])

        # 最適コストで更新
        dp_list[i] = min(dp_list[i], cost)

ans = dp_list[-1]
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [x for x in input().split()]
    for i in range(1, N+1):
        print(A.count(str(i)))
main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    l = [0]*N
    for i in A:
        l[i-1] += 1
    for j in l:
        print(j)
main()
### BUGGY CODE ###

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

mod = (10**9)+7
res = 0
for i in range(N-1):
    res += (A[i] * (sum(A[i+1:]) % mod)) % mod
    
print(res % mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A_j = sum(A)
mod = (10**9)+7
res = 0
for i in range(N-1):
    A_j -= A[i]
    res += (A[i] * (A_j % mod)) % mod

print(res % mod)
### BUGGY CODE ###

#coding:UTF-8

a,op,b = map(str,raw_input().split())
a = int(a)
b = int(b)

while True:
    if op == '+':
        print a + b
    elif op == '-':
        print a - b
    elif op == '*':
        print a * b
    elif op == '/':
        print a / b
    else:
        break

### FIXED CODE ###

#coding:UTF-8

while True:
    a,op,b = map(str,raw_input().split())
    a = int(a)
    b = int(b)
    if op == '+':
        print a + b
    elif op == '-':
        print a - b
    elif op == '*':
        print a * b
    elif op == '/':
        print a / b
    else:
        break
### BUGGY CODE ###

L = input()
n = len(L)
N = int(L)
ans = 0
mod = 10**9 + 7
for i in range(1,n+1):
    r = N % 10
    N = N // 10
    if r == 1:
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + 3**(i-1))%mod
    else:
        if i == 1:
            ans = 1
print(ans)

### FIXED CODE ###

L = input()
n = len(L)
mod = 10**9+7
pow3 = [1]
for i in range(1,n):
    x = (3*pow3[i-1])%mod
    pow3.append(x)
ans = 0
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + pow3[i-1])%mod
    else:
        if i == 1:
            ans = 1
print(ans)
### BUGGY CODE ###

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

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
print(A.count(1))

### FIXED CODE ###

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

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
          break
      break

print(A.count(1))
### BUGGY CODE ###

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

d=[[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split(' '))
    d[a-1][b-1]=c
    d[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                
dl=[[float('inf')]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= L:
            dl[i][j]=1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dl[i][j] > dl[i][k] + dl[k][j]:
                dl[i][j] = dl[i][k] + dl[k][j]

q=int(input())
for _ in range(q):
    s,t = map(int,input().split(' '))
    if dl[s-1][t-1]==float('inf'):
        print(-1)
    else:
        print(dl[s-1][t-1]-1)

### FIXED CODE ###

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

inf=10**10

d=[[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split(' '))
    d[a-1][b-1]=c
    d[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                
dl=[[inf]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= L:
            dl[i][j]=1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dl[i][j] > dl[i][k] + dl[k][j]:
                dl[i][j] = dl[i][k] + dl[k][j]

q=int(input())
for _ in range(q):
    s,t = map(int,input().split(' '))
    if dl[s-1][t-1]==inf:
        print(-1)
    else:
        print(dl[s-1][t-1]-1)
### BUGGY CODE ###

from math import ceil,floor
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  cnt1=0
  cnt2=0
  for i in range(k):
    if dd[i]==0:
      cnt1+=ceil((n-i-1)/k)
  a=x
  for i in range(k):
    a+=ceil((n-i-1)/k)*dd[i]
  cnt2=a//m-x//m
  print(n-1-cnt1-cnt2)

### FIXED CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  for i in range(k):
    if dd[i]==0:
      dd[i]=m
  s=x%m+sum(dd)*((n-1)//k)+sum(dd[:(n-1)%k])
  print(n-1-s//m)
### BUGGY CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

### FIXED CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

idx = [0] * (n-1)

for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        idx[i] = 1

for i in range(q):
    print(sum(idx[lr[i][0]-1:lr[i][1]-1]))



### FIXED CODE ###

n,q = map(int, input().split())
s = input()
# lr = [list(map(int, input().split())) for i in range(q)]

idx = [0] * n

# idx = [idx[i-1]+int(s[i-1:i+1] == "AC") for i in range(1, n)]
for i in range(1,n):
    idx[i] = idx[i-1] + (s[i-1:i+1] == "AC")


for i in range(q):
    l,r = map(int, input().split())
    print(idx[r-1]-idx[l-1])
### BUGGY CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    dams = list(map(int, input().split()))
    smallest_idx = 0
    for i in range(1,N):
        if dams[i] < dams[smallest_idx]:
            smallest_idx = i
    dams = dams[smallest_idx:] + dams[:smallest_idx]

    for i in range(0, dams[0]*2+1, 2):
        mts = [0]*N
        mts[0] = i
        for j in range(1,N):
            mts[j] = (dams[j-1]-mts[j-1]//2)*2
            if mts[j] < 0:
                break
        else:
            if mts[0]//2 + mts[N-1]//2 == dams[N-1]:
                mts = mts[N-smallest_idx:] + mts[:N-smallest_idx]
                print(*mts)
                return 0


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    dams = list(map(int, input().split()))
    S = sum(dams)
    res = [0]*N
    res[0] = S - 2*sum(dams[1:N:2])
    for i in range(1,N):
        res[i] = 2*dams[i-1]-res[i-1]
    print(*res)

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

import numpy as np
N = int(input())
S = np.array([list(input()) for i in range(N)])

ans = 0
flg = False
for a in range(N):
    S = np.roll(S, 1, axis=0)
    for i in range(N):
        for j in range(N):
            if S[i][j] != S[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)

### FIXED CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

ans = 0
flg = False
for a in range(N):
    S2 = S[a:] + S[:a]
    for i in range(N):
        for j in range(N):
            if S2[i][j] != S2[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)
### BUGGY CODE ###

from itertools import accumulate
N, M, K = map(int, input().split())
A = [0] + list(accumulate([int(i) for i in input().split()]))
B = [0] + list(accumulate([int(i) for i in input().split()]))
ans = 0
for n in range(N+1):
    a = A[n]
    for m in reversed(range(M+1)):
        if a + B[m] <= K:
            ans = max(ans, n+m)
            break
print(ans)

### FIXED CODE ###

import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))
ans = 0
j = len(B)-1
for i in range(len(SA)):
    while(j>=0):
        if SA[i] + SB[j] <= K:
            ans = max(ans,i+j)
            break
        j-=1
print (ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(len(bin(max(a)))-2):
  x = sum([1 for j in range(n) if ((a[j]>>i) & 1)])
  ans += x*(n-x)*(2**i)
  ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
ml = len(bin(max(a)))-2
ans = 0
for i in range(ml):
  x = sum([1 for j in a if ((j>>i) & 1)])
  ans += x*(n-x)*(2**i)
  ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(N):
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            break
    else:
        cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for i in range(1,1000001):
    if ex[i]>0:
        for j in range(i+i,1000001,i):ex[j]=0
        if ex[i]==1:
            cnt+=1
print(cnt)
### BUGGY CODE ###

from collections import deque
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = deque([0])
i = 0
count = 0
while a[i]-1 not in roop_find:
    roop_find.append(a[i]-1)
    i = a[i] - 1
    count += 1
b = roop_find.index(a[i]-1)

if k < b:
    print(list(roop_find)[k]+1)
else:
    k-=b
    e = k % (count+1-b)
    print(roop_find[b+e]+1)


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
pos = 0
visit = [0] * n
move = []
loop = []
while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        loop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1
if len(move) > k:
    print(move[k]+1)
else:
    print(loop[(k-(len(move)-len(loop)))%len(loop)]+1)
### BUGGY CODE ###

S=input()
l=len(S)
t=0

for k in range(4,l+1):
   for i in range(l-k+1):

      if int(S[i:(i+k)])%2019==0:
         t+=1
print(t)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    tmp=min(ans)
    a_list.append(tmp)
    graph[i][tmp-1]=N+1
    graph[j][tmp-1]=N+1
print(max(a_list))
for i in a_list:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N - 1)


def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1


dfs()
for i in ans:
    print(i)
### BUGGY CODE ###


def main():
    t = input()
    if t == "1":
        print(1)
        exit(0)
    li = [int(v) for v in input().split(' ')]
    s_li = sorted(li)
    count = 0
    c1 = 0
    for v in range(s_li[0] - 1, s_li[-1] + 1):
        t_c = 0
        c1 = s_li.count(v - 1)
        c2 = s_li.count(v)
        c3 = s_li.count(v + 1)

        t_c = c1 + c2 + c3
        if t_c > count:
            count = t_c
        if c1 != 0:
            s_li = s_li[s_li.index(v - 1):]
    print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
### BUGGY CODE ###

import math
from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

B=[]
for a in A:
    B.append(a//2)


Mb=lcm_list(B)
gmp=None

i=1
while True:
    m=Mb*i
    if m>M:
        break
    T=1
    for b in B:
        if not ((m//b)%2==1):
            T=0
    if T==1:
        gmp=m
        break
    
    i+=1


if gmp is None:
    print(0)
else:
    print(int(math.floor(M/gmp+1.0)/2.0))




### FIXED CODE ###

import math
from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

B=[]
for a in A:
    B.append(a//2)


Mb=lcm_list(B)
gmp=None


T=1
for b in B:
    if not (Mb//b)%2==1:
        T=0
if T==1:
    gmp=Mb




if gmp is None:
    print(0)
else:
    print(int(math.floor(M/gmp+1.0)/2.0))
### BUGGY CODE ###

MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)

### FIXED CODE ###

MOD=10**9+7
MAXN=4*(10**5)

two_power=[1 for _ in range(MAXN+10)]
for i in range(1, MAXN+10):
    two_power[i]=(two_power[i-1]*2)%MOD

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=two_power[2*n-1]
d=two_power[2*n-2]
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]

if m%2: print(-1); exit()

#L = [0]*n

g = [[] for _ in range(n)]
for i in range(m):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append((b-1,i))
    g[b-1].append((a-1,i))
#    L[a-1] += 1
#    L[b-1] += 1



used = [0]*m
def dfs(v):
    res = 0
    for (c,i) in g[v]:
        if used[i] == 1: continue
        used[i] = 1
        p =  dfs(c)
        if p%2 == 1:
            print(v+1,c+1)
        else:    
            print(c+1,v+1)
        res += p
    return res+1


for i in range(n):
    dfs(i)
#print(q)












### FIXED CODE ###

# coding: utf-8
# Your code here!
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]

if m%2: print(-1); exit()

#L = [0]*n

g = [[] for _ in range(n)]
for i in range(m):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append((b-1,i))
    g[b-1].append((a-1,i))
#    L[a-1] += 1
#    L[b-1] += 1



used = [0]*m
usedp = [0]*n
def dfs(v):
    res = 0
    for (c,i) in g[v]:
        if used[i] == 1: continue
        used[i] = 1
        if usedp[c] == 1:
            res += 1
            print(v+1,c+1)
            continue
        usedp[c] = 1
        p =  dfs(c)
        if p%2 == 1:
            print(v+1,c+1)
        else:    
            print(c+1,v+1)
        res += p
    return res+1


for i in range(n):
    dfs(i)
#print(q)
### BUGGY CODE ###

def func1(S):
  tmp = ''
  for i in range(len(S)):
    tmp = tmp + S[len(S)-1-i]
  return tmp
S = input()
Q = int(input())
rev = False
for i in range(Q):
  query = input().split()
  if query[0] == '1':
    rev = not rev
  elif query[0] == '2':
    if query[1] == '1':
      if rev == False:
        S = query[2] + S
      else:
        S = S + query[2]
    elif query[1] == '2':
      if rev == False:
        S = S + query[2]
      else:
        S = query[2] + S
  #print('S='+S)
if rev == True:
  S = func1(S)
print(S)

### FIXED CODE ###

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
	a.append(int(input()))
k=max(a)
for j in range(N):
	b=a[:j]+a[j+1:]
	if k in b:
		print(k)
	else:
		print(max(b))

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
	a.append(int(input()))
k=max(a)
count=0
for j in range(N):
	if count==1:
		print(k)
	else:
		if a[j]==k:
			b=a[:j]+a[j+1:]
			count=1
			print(max(b))
		else:
			print(k)
### BUGGY CODE ###

#112_D
N,M=map(int,input().split())
Ans=1
for i in range(2,M//N+1):
    if M%i==0:
        Ans=i
print(Ans)

### FIXED CODE ###

#112_D
N,M=map(int,input().split())
#M//N以下のMの約数の最大
divisors=[]
for i in range(1,int(M**.5)+1):
    if M%i==0:
        divisors.append(i)
        if i!=(M//i):
            divisors.append(M//i)
Ans=1
for x in sorted(divisors):
    if M//N>=x:
        Ans=x
    else:
        break
print(Ans)
### BUGGY CODE ###

import sys
import re
lines = sys.stdin.readlines()
for line in lines[2:]:
    l, r = map(int, line.split())
    match = re.findall("(AC)", lines[1][l-1:r])
    print(len(match))

### FIXED CODE ###

n, q = map(int, input().split())
S = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if S[i : i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

#ABC154C

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

ave = 0
j = 0

for i in range(n-2):
    temp = p[i:i+k]
    _ave = (sum(temp))/k
    if _ave>=ave:
        ave = _ave
        j = i

import numpy as np
d = np.array(p[j:j+k])
kitai = sum((1+d))/2

# 計算量がO(K)を再計算しているため NG
# kitai = 0
# for x in p[j:j+k]:
#     kitai += sum(range(1,x+1))/x

print(kitai)

### FIXED CODE ###

#ABC154C

n, k = list(map(int,input().split()))
p = [((int(x)+1)/2) for x in input().split()]

ave = sum(p[0:k])
max = ave
for i in range(n-k):
    ave = ave-p[i]+p[k+i]
    if ave > max:
        max = ave
print(max)