Harryxun/stf_run huggingface dataset:
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ps = [0] * N
for p,x in PX:
    ps[p-1] += x

ans = [0] * N
def dfs(v,p=-1, c=0):
    ans[v] = c + ps[v]
    for to in es[v]:
        if to==p: continue
        dfs(to, v, ans[v])
dfs(0)
print(*ans)

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

xs = [0] * N
for p,x in PX:
    xs[p-1] += x

ans = [0] * N
ans[0] = xs[0]
visited = [0] * N
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
        ans[to] = ans[v] + xs[to]

print(*ans)
H,W = map(int,input().split())

if H < 10**9:
    if H % 2 == 0:
        sum = W * H / 2
    elif W % 2 == 0:
        sum = (W * (H-1) / 2) + (W / 2)
    else:
        sum = (W * (H-1) / 2) + ((W+1) / 2)
else:
    1+1

print(int(sum))

### FIXED CODE ###

H,W = map(int,input().split())
 
if (H == 1)or(W == 1):
    sum = 1
elif H % 2 == 0:
    sum = W * H // 2
elif W % 2 == 0:
    sum = (W * (H-1) // 2) + (W // 2)
else:
    sum = (W * (H-1) // 2) + ((W+1) // 2)
 
print(int(sum))
n = int(input())
s = input()

start = s.index("#")
black = s[start:].count("#")
white = s[start:].count(".")

print(min(black, white))

### FIXED CODE ###

n = int(input())
s = input()
black = s[:0].count("#")
white = s[0:].count(".")
count = [black+white]    
    
for i in range(1, n+1):
    if s[i-1]== "#":
        black +=1
    else:
        white -=1
    count.append(white+black)
    
print(min(count))
n = int(input())
a = list(map(int,input().split()))
global count
count = 0
def solve(a):
    count += 1
    if count > 10**7:
        print('NO')
        exit()
    if min(a) < 0:
        return False

    for i in range(n):
        if a[i] != 0:
            break
        if i == n-1:
            return True

    for i in range(n):
        b = []
        for j in range(n):
            c = a[(i+j)%n]-j-1
            b.append(c)

        if solve(b):
            return True

if solve(a):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

if sum(a) % (n*(n+1)//2) != 0:
    print('NO')
    exit()
else:
    k = sum(a)// (n*(n+1)//2)


for i in range(n-1):
    d = a[i+1] - a[i] - k

    if d > 0 or d % n != 0:
        print('NO')
        exit()

print('YES')
#!/usr/bin/env python3


N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A = sorted(A)[::-1]
total = sum(A)
print(A[M-1])
if A[M] < total * (1 / (4 * M)):
    print('No')
else:
    print('Yes')


### FIXED CODE ###

# A = [int(x) for x in line2.split()]

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]


A = sorted(A)[::-1]
total = sum(A)
thre = total * (1 / (4*M))
if A[M-1] < thre:
    print('No')
else:
    print('Yes')
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=list(map(lambda a:f(a),List[x]))
  L.sort(key=lambda x:-x)
  res=0
  for i in range(len(L)):
    res=max(res,L[i]+i+1)
  return res
print(f(0))
  

### FIXED CODE ###

import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))
A, P = map(int, input().split())

a = A*3 + P

if a > 0:
  print(math.floor(a/2))
else:
  print(0)

### FIXED CODE ###

A, P = map(int, input().split())

a = A*3 + P

if a > 0:
  print(int(a/2))
else:
  print(0)
r1,c1,r2,c2=map(int,input().split())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p=10**9+7
N=2*10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print((cmb(r2+1+c2+1,c2+1,p)-cmb(r1+c2+1,c2+1,p)-cmb(r2+1+c1,c1,p)+cmb(r1+c1,c1,p))%p)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p=10**9+7
N=2*10**6+10
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print((cmb(r2+1+c2+1,c2+1,p)-cmb(r1+c2+1,c2+1,p)-cmb(r2+1+c1,c1,p)+cmb(r1+c1,c1,p))%p)
N=input()
A=input()
B=N%500
if(int(B)-int(A))==0):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N=int(input())
A=int(input())
N!=0
B=int(N%500)
if(B <= A):
    print("Yes")
else:
    print("No")
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
  if x>=a[i]:
    ans+=1
    x-=a[i]
if x=sum(a): ans=n-1
print(ans)


### FIXED CODE ###

def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
    
n,x=MI()
a=LI()
a.sort()
y=x
ans,s=0,0
for i in range(n):
    s+=a[i]
    if s>x:
        break
    else:
        if i<n-1:
            ans+=1
        elif x-s==0:
            ans+=1
            
print(ans)
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = np.array(rl())
A_cummin = A.minimum.accumulate(A)
B = A - A_cummin

answer = (B == B.max()).sum()
print(answer)

### FIXED CODE ###

import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = rl()
answer = 1
profit = 0
min = A[0]
for i in range(1, N):
    if A[i] < min:
        min = A[i]
        continue
    x = A[i] - min
    if x > profit:
        answer = 1
        profit = x
    elif x == profit:
        answer += 1

print(answer)
# 40
l=[]
total=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        l.append((t//10+1)*10-t)
a=max(l)
print(total-a)

### FIXED CODE ###

l=[]
total=0
a=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        a=max(a,10-(t%10))
print(total-a)
s = input()
a = ['A', 'C', 'G', 'T']
ans = []
k = 0
for i in range(len(s)):
  if s[i] in a:
    k += 1
  else:
    ans.append(k)
    k = 0
print(max(ans))

### FIXED CODE ###

s = input()
a = ['A', 'C', 'G', 'T']
ans = []
k = 0
for i in range(len(s)):
  if s[i] in a:
    k += 1
  else:
    ans.append(k)
    k = 0
ans.append(k)
print(max(ans))
def dist(X1,X2):
  d=X1-X2
  d=[x**2 for x in d]
  d=sum(d)
  return d
 
count=int(0)
N,D=map(int,input().split())
X=list(range(N))
for i in range(N):
  X[i]=list(map(int,input().split()))
for i in range(N):
  for j in range(i+1,N):
    d=dist(X[i],X[j])
    if isinstance(d,int):
      count=count+1
print(count)

### FIXED CODE ###

import math

def dist(X1,X2):
  d=[abs(X1[i]-X2[i]) for i in range(len(X1))]
  d=[x**2 for x in d]
  d=sum(d)
  d=math.sqrt(d)
  return d
 
count=int(0)
N,D=map(int,input().split())
X=list(range(N))
for i in range(N):
  X[i]=list(map(int,input().split()))
for i in range(N):
  for j in range(i+1,N):
    d=dist(X[i],X[j])
    if d.is_integer():
      count=count+1
print(count)
import numpy as np
import math

def main():
    N, X = map(int, input().split())
    x = np.asarray(list(map(int, input().split())))
    x = np.absolute(x - X)
    if N > 1:
        d = np.absolute(x[:N-1] - x[1:N])
        l = None
        for i, n in enumerate(d):
            if i == 0:
                l = n
            else:
                l = math.gcd(l, n)
        print(l)
    else:
        print(x[0])


if __name__ == '__main__':
    main()))

### FIXED CODE ###


import numpy as np
import fractions

def main():
    N, X = map(int, input().split())
    x = np.asarray(list(map(int, input().split())))
    x = np.absolute(x - X)
    if N > 1:
        l = None
        for i, n in enumerate(x):
            if i == 0:
                l = n
            else:
                l = fractions.gcd(l, n)
        print(l)
    else:
        print(x[0])


if __name__ == '__main__':
    main()
a, b, c = list(map(int, input().split()))
if a > 0 and b > 0 and c > 0:
  if 4*a*b < (c-a-b)**2:
  print('Yes')
  else:
  print('No')
else:
  print('')

### FIXED CODE ###

import math
a,b,c = map(int,input().split())
l = 4*a*b
r = (c-a-b)**2
if (a+b >= c):
    print("No")
else:
    if(l < r):
        print("Yes")
    else:
        print("No")
import collections
n, m = map(int, input().split())
L = []
for _ in range(m):
    a, b = map(int, input().split())
    L.append(a)
    L.append(b)

L_dict = collections.Counter(L)
L_dict_sort = sorted(L_dict.items(), key=lambda x:x[0])
for i in range(n):
    print(L_dict_sort[i][1])

### FIXED CODE ###

n, m = map(int, input().split())
L = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    L[a - 1] += 1
    L[b - 1] += 1

for i in L:
    print(i)
S = input()
l = len(S)

S1 = S[0:(l-1)//2]
S2 = S[(l+3)//2]

def Kaibun(Str):
	if Str == Str[::-1]:
		return True
	else:
		return False

if Kaibun(S) and Kaibun(S1) and Kaibun(S2):
	print("Yes")
else:
	print("No")

### FIXED CODE ###

def f(x):
  return x==x[::-1]
S=input()
n=(len(S)-1)//2
S1,S2=S[:n],S[n+1:]
if f(S) and f(S1) and f(S2):
  print('Yes')
else:
  print('No')
def binary(list_a,item):
  low=0
  high=len(list_a)-1
  while (high-low)>1:
    mid=int((low+high)/2)
    tmp=list_a[mid]
    if tmp>item:
      high=mid
    elif tmp<item:
      low=mid
    elif tmp==item:
      eq=[i for i, x in enumerate(list_a) if x == tmp]
      high=eq[-1]
      low=eq[0]
      return low-1,high+1
  return low,high

def main():
  N=int(input())
  A=sorted(list(map(int,input().split())))
  B=sorted(list(map(int,input().split())))
  C=sorted(list(map(int,input().split())))
  ans=0
  for b in B:
    a_low,a_high=binary(A,b)
    c_low,c_high=binary(C,b)
    
    if b>A[a_high]:
      a_low=N-1
    elif b<A[a_low]:
      a_low=0
      
    if b<C[c_low]:
      c_high=0
    elif b>C[c_high]:
      c_high=N
    
    ans+=(a_low+1)*(N-c_high)
  print(ans)
  
if __name__=="__main__":
  main()

### FIXED CODE ###

import bisect

def main():
  N=int(input())
  A=sorted(list(map(int,input().split())))
  B=sorted(list(map(int,input().split())))
  C=sorted(list(map(int,input().split())))
  ans=0
  for b in B:
    a=bisect.bisect_left(A,b)
    c=N-bisect.bisect_right(C,b)
    ans+=a*c
  print(ans)
  
if __name__=="__main__":
  main()
import math

def num_divisors(n):
    return reduce(lambda x, y: x * (y[1] + 1), factorize(n), 1)

def factorize(n):
    f = ()
    for m in gen_prime_candidates():
        if m * m > n:
            break
        e, n = calc_exp(n, m)
        if e:
            f = f + ( (m, e), )
    if n != 1:
        f = f + ( (n, 1), )
    return f

n = int(raw_input())
nx = factorial(n)

print num_divisors(nx) % 10**9 + 7


### FIXED CODE ###

import math

def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff

def divisor_num(n):
    a = 1
    for _ , x in factorization(n):
        a *= x + 1
    return a

n = int(raw_input())
nx = math.factorial(n)
print divisor_num(nx) % (10**9 + 7)
N=int(input())
S=list(input())
a=list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
res=''
for s in S:
  code=a[i]+N
  if code>a.index('z'):
    code-=(a.index('z')-1)
  res+=code
print(res)

### FIXED CODE ###

N=int(input())
S=list(input())
a=list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
res=''

for s in S:
  code=a.index(s)+N
  if code>a.index('Z'):
    code-=26
  res+=a[code]
print(res)
s = raw_input()
n = len(s)
if not n & 1:
    l = n / 2 - 1
    r = n / 2
    res = n / 2
    while r < n and l >= 0 and s[l] == s[r]:
        l -= 1
        r += 1
        res += 1
    print res
else:
    l = n / 2 - 1
    r = n / 2 + 1
    res = n / 2 + 1
    if s[n / 2] != s[l] or s[n / 2] != s[r]:
        print res
    else:
        while r < n and l >= 0 and s[l] == s[r]:
            l -= 1
            r += 1
            res += 1
        print res

### FIXED CODE ###

s = raw_input()
n = len(s)
if n == 1:
    print 1
    exit()
if not n & 1:
    l = n / 2 - 1
    r = n / 2
    res = n / 2
    while r < n and l >= 0 and s[l] == s[r]:
        l -= 1
        r += 1
        res += 1
    print res
else:
    l = n / 2 - 1
    r = n / 2 + 1
    res = n / 2 + 1
    if s[n / 2] != s[l] or s[n / 2] != s[r]:
        print res
    else:
        while r < n and l >= 0 and s[l] == s[r]:
            l -= 1
            r += 1
            res += 1
        print res
import itertools
def getCombList(xList):
  N = len(xList)
  result = []
  for n in range(1,N+1):
    for conb in itertools.combinations(xList, n):
      result.append(list(conb)) #タプルをリスト型に変換
  #print(result)
  return result

import sys
sys.setrecursionlimit(20000)

import numpy as np
L1 = input()
H, W, K = map(int, L1.split(" "))
mat = np.zeros([H,W], dtype="int32")
for i in range(H):
  Li = input()
  for j, s in enumerate(Li):
    if s == "#":
      mat[i,j] = 1

if np.sum(np.sum(mat)) < K:
  print(0)
else:
  if np.sum(np.sum(mat)) == K:
    c = 1
  else:
    c = 0
  matp = mat.copy()
  HList = list(range(H))
  WList = list(range(W))
  HcombList = getCombList(HList)
  WcombList = getCombList(WList)
  for Hcomb in HcombList:
    for Wcomb in WcombList:
      matp[Hcomb, :] = 0
      matp[:, Wcomb] = 0
      if np.sum(np.sum(matp)) == K:
        c = c + 1
      matp = mat.copy()
      
  for Hcomb in HcombList:
    matp[Hcomb, :] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

  for Wcomb in WcombList:
    matp[:, Wcomb] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

print(c)

### FIXED CODE ###

import itertools
def getCombList(xList):
  N = len(xList)
  result = []
  for n in range(1,N+1):
    for conb in itertools.combinations(xList, n):
      result.append(list(conb)) #タプルをリスト型に変換
  #print(result)
  return result

import numpy as np
L1 = input()
H, W, K = map(int, L1.split(" "))
mat = np.zeros([H,W], dtype="int32")
for i in range(H):
  Li = input()
  for j, s in enumerate(Li):
    if s == "#":
      mat[i,j] = 1

if np.sum(np.sum(mat)) < K:
  print(0)
else:
  if np.sum(np.sum(mat)) == K:
    c = 1
  else:
    c = 0
  matp = mat.copy()
  HList = list(range(H))
  WList = list(range(W))
  HcombList = getCombList(HList)
  WcombList = getCombList(WList)
  for Hcomb in HcombList:
    for Wcomb in WcombList:
      matp[Hcomb, :] = 0
      matp[:, Wcomb] = 0
      if np.sum(np.sum(matp)) == K:
        c = c + 1
      matp = mat.copy()
      
  for Hcomb in HcombList:
    matp[Hcomb, :] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

  for Wcomb in WcombList:
    matp[:, Wcomb] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

  print(c)
# -*- coding: utf-8 -*-

import numpy as np

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

a = np.array(list(map(int, input().split())))
for i in range(n[0] - 1):
    a = np.vstack((a, list(map(int, input().split()))))

b = np.array(list(map(int, input().split())))
for i in range(n[1] - 1):
    b = np.vstack((b, list(map(int, input().split()))))

ab_sum = np.dot(a, b)
for i in range(n[0]):
    print(ab_sum[i])



### FIXED CODE ###

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

for i in range(n[0]):
    a.append(list(map(int, input().split())))

for i in range(n[1]):
    b.append(int(input()))

for i in range(n[0]):
    ab_sum = 0
    for j in range(n[1]):
        ab_sum += a[i][j] * b[j]
    print(ab_sum)
from math import pow
a, b, c = map(int, input().split())
mod = 10**9+7
if 4*a*b < pow(c-a-b, 2, mod):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c = map(int, input().split())
if (c-a-b) ** 2 - 4*a*b > 0 and c-a-b > 0:
    print('Yes')
else:
    print('No')
A,B,K = map(int,input().split())
list1 = list(range(A,B+1))
for i in list1:
	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)
import math
from decimal import *

sa, sb = input().split()
a = Decimal(sa)
b = float(sb)
lb = Decimal(b * 100)

ans = Decimalc(Decimal(a * lb) // Decimal(100))
print(int(ans))


### FIXED CODE ###

import math
from decimal import *

sa, sb = input().split()
a = Decimal(sa)
b = Decimal(sb)
lb = Decimal(b * Decimal(100))

ans = Decimal(Decimal(a * lb) // Decimal(100))
print(int(ans))
print(input()*'ACL')

### FIXED CODE ###

print(int(input())*'ACL')
N = int(input().rstrip())
a = input().rstrip().split(' ')
num = 0
for i in range(0, N, 1):
  if a[i] % 2 == 1:
    num += 1
print(num)

### FIXED CODE ###

N = int(input().rstrip())
a = input().rstrip().split(' ')
num = 0
for i in range(0, N, 2):
  if int(a[i]) % 2 == 1:
    num += 1
print(num)
s=list(input())
t=list(input())
sl=len(s)
tl=len(t)
for k in range(sl-tl+2):
    judge=True
    for i in range(tl):
        if s[i+k]==t[i] or s[i+k]=="?":
            pass
        else:
            judge=False
            break
    if judge:
        for i in range(tl):
            s[i+k]=t[i]
        for i in range(sl):
            if s[i]=="?":
                s[i]="a"
        print("".join(s))
        exit()
print("UNRESTORABLE")


### FIXED CODE ###

s=list(input())
t=list(input())
sl=len(s)
tl=len(t)
for k in range(sl-tl,-1,-1):
    judge=True
    for i in range(tl):
        if s[i+k]==t[i] or s[i+k]=="?":
            pass
        else:
            judge=False
            break
    if judge:
        for i in range(tl):
            s[i+k]=t[i]
        for i in range(sl):
            if s[i]=="?":
                s[i]="a"
        print("".join(s))
        exit()
print("UNRESTORABLE")
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 1
    j = 0
    for i in t:
        ind = bisect.bisect_right(d[i], j)
        m += d[i][ind] - j
        if d[i][ind] > n:
            j = d[i][ind] - n
        else:
            j = d[i][ind]
    return m
print(main())


### FIXED CODE ###

def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())
# input
N = int(input())
noguchi = [1000 * n for n in range(1, 11)]

# check
print(min([ngc - N for ngc in noguchi if (ngc - N) < 0]))


### FIXED CODE ###

# input
N = int(input())
noguchi = [1000 * n for n in range(1, 11)]

# check
print(min([ngc - N for ngc in noguchi if (ngc - N) >= 0]))
import math

n, m = map(int, input().split())
c = 0
f = [math.floor(n/2), math.floor(n/2) + 1]
if n % 2 == 0:
    while c < m:
        c += 1
        if c == math.ceil((n/4)　+ 1):
            if (f[1] + 1) % n == 0:
                f[1] = n
            else:
                f[1] = (f[1] + 1) % n
        print(str(f[0]) + ' ' + str(f[1]))
        if (f[0] - 1) % n == 0:
            f[0] = n
        else:
            f[0] = (f[0] - 1) % n
        if (f[1] + 1) % n == 0:
            f[1] = n
        else:
            f[1] = (f[1] + 1) % n
else:
    while c < m:
        c += 1
        print(str(f[0]) + ' ' + str(f[1]))
        if (f[0] - 1) % n == 0:
            f[0] = n
        else:
            f[0] = (f[0] - 1) % n
        if (f[1] + 1) % n == 0:
            f[1] = n
        else:
            f[1] = (f[1] + 1) % n

### FIXED CODE ###

import math

n, m = map(int, input().split())
c = 0
f = [math.floor(n/2), math.floor(n/2) + 1]
if n % 2 == 0:
    while c < m:
        c += 1
        if c == math.floor(n/4) + 1:
            if (f[1] + 1) % n == 0:
                f[1] = n
            else:
                f[1] = (f[1] + 1) % n
        print(str(f[0]) + ' ' + str(f[1]))
        if (f[0] - 1) % n == 0:
            f[0] = n
        else:
            f[0] = (f[0] - 1) % n
        if (f[1] + 1) % n == 0:
            f[1] = n
        else:
            f[1] = (f[1] + 1) % n
else:
    while c < m:
        c += 1
        print(str(f[0]) + ' ' + str(f[1]))
        if (f[0] - 1) % n == 0:
            f[0] = n
        else:
            f[0] = (f[0] - 1) % n
        if (f[1] + 1) % n == 0:
            f[1] = n
        else:
            f[1] = (f[1] + 1) % n
i = 2
while True:
    cond = i * 4
    all_primes = primes + prime_decomposition(i)
    total = reduce(lambda x, y: x * y, all_primes)
    candi_primes = [p for p in all_primes if p <= cond - 2]

    r = find_result(candi_primes, cond, total)
    if r is not None:
        h, n, w = r
        print '{} {} {}'.format(int(total/h), int(total/n), int(total/w))
        break
    i += 1

### FIXED CODE ###

# coding: utf-8
from itertools import combinations


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


def find_result(primes, cond, total):
    combi = {}
    for i in range(len(primes)):
        for c in combinations(primes, i+1):
            s = reduce(lambda x, y: x * y, c)
            if s <= cond - 2 and total / s < 3500:
                combi[tuple(c)] = s

    keys = sorted(combi.keys())
    for h in keys:
        for n in keys:
            for w in keys:
                s = combi[h] + combi[n] + combi[w]
                if s == cond:
                    return combi[h], combi[n], combi[w]
    return None


N = int(raw_input())
primes = [
    1,
] + prime_decomposition(N)

i = 2
while True:
    cond = i * 4
    all_primes = primes + prime_decomposition(i)
    total = reduce(lambda x, y: x * y, all_primes)
    candi_primes = [p for p in all_primes if p <= cond - 2]

    r = find_result(candi_primes, cond, total)
    if r is not None:
        h, n, w = r
        print '{} {} {}'.format(int(total/h), int(total/n), int(total/w))
        break
    i += 1
import math
n = int(input())
t = map(int, input())
bottle_neck = min(t)[0]
ti = math.ceil(n/bottle_neck)
print(ti+4)



### FIXED CODE ###

#a,b,c = map(int,inpput().split(" "))
#n = int(input())
#print(a,b,c)
t=[]
for i in range(5):
    t.append(int(input()))
n = int(input())
flag = True
for i in range(5):
    for j in range(5-i-1):
        if abs(t[i]-t[j+i+1]) >n:
            flag =False
            break
if not flag:
    print(":(")
else:
    print("Yay!")
N = int(input())
l = [105, 135, 165, 189, 195]
for i in range(5):
    if N < l[i]:
        print(i)
        exit(1)
print(5)


### FIXED CODE ###

N = int(input())
l = [105, 135, 165, 189, 195]
for i in range(5):
    if N < l[i]:
        print(i)
        exit()
print(5)