Harryxun/stf_run huggingface dataset:
s = int(input())
def func(n):
  if n%2 == 1:
    return 3n+1
  else:
    return n/2
def prog(N):
  if N == 1:
    return s
  else:
    a=s
    for i in range(1,N):
      a = func(a)
    return a


while prog(k)==prog(j):
  



### FIXED CODE ###

s = int(input())
def func(n):
  if n%2 == 1:
    return 3*n+1
  else:
    return n//2
def prog(N):
  if N == 1:
    return s
  else:
    a=s
    for i in range(1,N):
      a = func(a)
    return a

b=[]
for i in range(1,1000000):
  tmp = prog(i)
  if tmp in b:
    print(i)
    break
  else:
    b.append(tmp)
m1,m2,d1,d2=map(int,input().split())
if d2==1 and (d2-d1==1 or d2-d1==-11):
  print(1)
else:
  print(0)

### FIXED CODE ###

m1,d1=map(int,input().split())
m2,d2=map(int,input().split())
if d2==1:
  print(1)
else:
  print(0)
def calc(x,y):
    i = len(x)
    j = len(y)
    if d[i][j]:
        return d[i][j]
    else:
        if i == 1:
            if x in y:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        elif j == 1:
            if y in x:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        else:
            if x[-1] == y[-1]:
                tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
            else:
                tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[None for _ in range(len(y)+1)] for _ in range(len(x)+1)]
    print(calc(x,y))


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
n = int(input())
lis = map(int,input().split())

ans = "Yes"
for i in range(1,n):
	if lis[i] - lis[i-1] <= 1:
		pass
	else:
		ans = "No"
		break

print(ans)

### FIXED CODE ###

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

a = "Yes"
m = 0

for i in range(n):
	if m - h[i] > 1:
		a ="No"
		break
	else:
		m = max(m,h[i])
print(a)
import itertools
import collections
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n-1)]
xy_1d = list(itertools.chain.from_iterable(xy))
c = collections.Counter(xy_1d)
cc = c.most_common()
num_max = cc[0][0]
color = cc[0][1]
color_list = [i+1 for i in range(color)]
length = len(xy)
l = [color]
for i in range(length):
    if i < color:
        l.append(color_list[i])
    elif i >= color:
        num = i - int(length/color)*color
        l.append(color_list[num])
for j in l:
    print(j)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
 
N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
    V[a].add(b)
    V[b].add(a)
#print(V)
maxc = 0
for v in V:
    maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
    CE[e] = 0
#print(CE)
 
def dfs(u,t,c):
    if t > 0:
        CE[(min(u,t),max(u,t))] = c
    cc = c+1
    if cc > maxc:
        cc = 1
    for v in V[u]:
        if CE[(min(u,v),max(u,v))] == 0:
            dfs(v,u,cc)
            cc += 1
            if cc > maxc:
                cc = 1
dfs(1,0,1)
print(maxc)
for e in E:
    print(CE[e])
import numpy as np
N=int(input())
l=[list(map(int, input().split())) for i in range(N-1)]

net=np.zeros((N+1, N+1))
for i in range(N-1):
  net[l[i][0], l[i][1]]=1
  
net=net+net.T
num_c=np.max(np.sum(net, axis=1))

print(int(num_c))

c_net=np.zeros((N+1, N+1, num_c))
for i in range(N-1):
  a=l[i][0]
  b=l[i][1]
  
  j=0
  while np.sum(c_net[a, :, j]==1)>0 or np.sum(c_net[b, :, j]==1)>0:
    j+=1
    if j>=num_c-1:
      break
    
  c_net[a, b, j]=1
  c_net[b, a, j]=1
  print(j+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N=int(input())
ab=[list(map(int, input().split())) for i in range(N-1)]
link=[[] for i in range(N+1)]
for i in range(0, N-1):
  link[ab[i][0]].append([ab[i][1], i])
  link[ab[i][1]].append([ab[i][0], i])
  
out=[0]*(N-1)
def f(num, prenum=0, prec=0):
  postc=1
  for postnum, linknum in link[num]:
    if postnum==prenum:
      continue
    if postc==prec:
      postc+=1
      
    out[linknum]=postc
    f(postnum, num, postc)
    postc+=1
    
f(1)

print(max(out))
for i in range(N-1):
  print(out[i])
from functools import reduce
from collections import Counter

N, X = map(int, input().split())
loc = list(map(int, input().split()))
mem = {}

def prime_factors(n):
    if mem.get(n) is not None:
        return mem[n]
    else:
        i = 2
        factors = []
        while i*i <= n:
            if n % i == 0:
                factors.append(i)
                n = n // i
            else:
                i += 1
        if n > 1:
            factors.append(n)
        mem[n] = factors
    return factors


def find_shared_factors(factor1, factor2):
    counters = [Counter(factor1), Counter(factor2)]
    if len(factor2) == 0:
        return factor1
    elif len(factor1) == 0:
        return factor2
    else:
        return list(reduce(lambda x,y: x&y, counters).elements())

factors = []
for l in loc:
    factors = find_shared_factors(prime_factors(abs(l-X)), factors)
for i in range(N):
    for j in range(N):
        if i < j:
            factors = find_shared_factors(prime_factors(abs(loc[i]-loc[j])), factors)

r = reduce(lambda x,y: x*y, factors)

print(r)

### FIXED CODE ###

from functools import reduce
N, X = map(int, input().split())
loc = list(map(int, input().split()))


def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


print(reduce(gcd, [abs(l-X) for l in loc]))
n, k = map(int, input().split())
a = input().split()

for i in range(10*n - n):
    c = str(n+i)
    
    for j in a:
        if j in c:
            break
    
    else:
        ans = c
        break
        
print(ans)

### FIXED CODE ###

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

for i in range(10*n - n):
    c = str(n+i)
    
    for j in a:
        if j in c:
            break
    
    else:
        ans = c
        break
        
print(ans)
N,K = map(int,input().split())
P = [int(input()) for i in range(N)]
Q = []*N
for i in range(N):
  Q[i] = (P[i]+1)/2
R = sum(Q[:K])
ans = R
for j in range(N-K):
  R = R - Q[j] + Q[j+K]
  ans = max(ans,R)
print(ans)

### FIXED CODE ###

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

ANS=[0]*5
flag=0

if N<100000:
    if N<10000:
        if N<1000:
            if N<100:
                if N<10:
                    ANS[0]=int(N%10)
                    flag=flag+1
                ANS[1]=9
                flag=flag+1
            ANS[2]=9+N-100+1
            flag=flag+1
        ANS[3]=909
        flag=flag+1
    ANS[4]=9+900+N-10000+1
    flag=flag+1
elif N==100000:
    print(90909)

if flag==5:
    print(ANS[0])
if flag==4:
    print(ANS[1])
if flag==3:
    print(ANS[2])
if flag==2:
    print(ANS[3])
if flag==1:
    print(ANS[4])

### FIXED CODE ###

x=input().split()

y=[0]*3

for i in range(3):
  y[i]=int(x[i])

ans=(y[2]-(y[0]-y[1]))

if ans>0:
  print(ans)
  
elif ans<=0:
  print(0)
n=int(input())
stones=list(map(int, input.split()))
infini=(10**4)*(10**5)
dp = [infini for _ in range(n)]
dp[0]=0
dp[1]=stones[1]
for pos in range(2, n):
   dp[pos] = min(dp[pos], stones[pos] + min(dp[pos-1], dp[pos-2]))
print(dp[-1])

### FIXED CODE ###


n=int(input())
stones=list(map(int, input().split()))
infini=(10**4)*(10**5)
dp = [infini for _ in range(n)]
dp[0]=0

for pos in range(0, n-1):
   dp[pos+1] = min(dp[pos+1], dp[pos] + abs(stones[pos] - stones[pos+1]))
   if pos <= n-3:
      dp[pos+2] = min(dp[pos+2], dp[pos] + abs(stones[pos] - stones[pos+2]))
print(dp[-1])
A, B = map(int,input(),split())
if A+B >= 10:
  print('error')
else:
  print(A+B)

### FIXED CODE ###

A, B = map(int,input().split())
if A+B >= 10:
    print('error')
else:
    print(A+B)
import sys

args = sys.argv

list = {'Sunny':'Cloudy', 'Cloudy':'Rainy', 'Rainy':'Sunny'}

print(list[args[1]])

### FIXED CODE ###

weather = input()

list = {'Sunny':'Cloudy', 'Cloudy':'Rainy', 'Rainy':'Sunny'}

print(list[weather])
import numpy
n = int(input())
ls = [int(input()) for _ in range(n)]
if 0 in ls:
    print(0)
res = numpy.prod(ls)
elif res > 10**18:
    print(-1)
else:
    print(numpy.prod(ls))


### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
a = int(input())
b = int(input())

print(a < b)
print(a > b)
print(a == b)

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")
cnt = 0
base = 0
MOD = 2019

for d in input().rstrip():
    base *= 10
    base += int(d)
    tmp = base
    while tmp:
        if tmp % MOD == 0:
            cnt += 1
        tmp //= 10
print(ans)

### FIXED CODE ###

s = input().rstrip()
tmp = 0
pw = 1
from collections import Counter
c = Counter()
c[0] += 1

for d in s[::-1]:
    tmp += int(d) * pw
    tmp %= 2019
    pw *= 10
    pw %= 2019
    c[tmp] += 1

print(sum([v*(v-1)//2 for v in c.values() if v > 1]))
x = input()
answer = x ** 3
print(answer)

### FIXED CODE ###

x = input()
answer = int(x) ** 3
print(answer)
S = input()
queryNum = input()
for i in queryNum:
	order = input()
	if order == 1:
		S = S[::-1]
	else:
		if order[0] == 1:
			S = order[2] + S
		else:
			S = S + order[2]
print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
queryNum = input()
flip = False
for i in range(int(queryNum)):
	order = input()
	if order == '1':
		if flip:
			flip = False
		else:
			flip = True
	else:
		if order[2] == '1':
			if not flip:
				S.appendleft(order[4])
			elif flip:
				S.append(order[4])
		else:
			if not flip:
				S.append(order[4])
			elif flip:
				S.appendleft(order[4])
S = ''.join(S)
if flip:
	print(S[::-1])
else: 
	print(S)
# -*- coding: utf-8 -*-
import math
import itertools
import numpy as np
import sys
input = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return set(divisors)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    a, b = map(int, input().split())

    divisors = []
    max_divisor = math.gcd(a, b)

    divisors = make_divisors(max_divisor)

    _, table = sieve(max(divisors))

    result = divisors & set(table)

    print(divisors)
    print(result)

    size = len(result) + 1
    print(size)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import fractions


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


def main():
    a, b = map(int, input().split())

    gcd = fractions.gcd(a, b)
    table = prime_factorization(gcd)
    print(len(table) + 1)


if __name__ == "__main__":
    main()
l,s = [],[]
for i in range(5):
    num = int(input())
    l.append(num)
    s.append(num%10)
res = 0
s = list(set(s))
if 0 in s:
    s.remove(0)
for i in l:
    res += ((i+9)//10*10)
else:
    print(res-(10-min(s)))

### FIXED CODE ###

l,s = [],[]
for i in range(5):
    num = int(input())
    l.append(num)
    if num%10!=0:
        s.append(num%10)

res = 0

for i in l:
    if i%10!=0:
        res += (i+10)//10*10
    else:
        res += i
else:
    if len(s) != 0:
        tmp = min(s)
    else:
        tmp = 10
    print(res-(10-tmp))
N = int(input())
S = input()
K = int(input())

ans = ''
for i in S:
    if i == S[K]
        ans += i
    else:
        ans += '*'

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
K = int(input()) - 1
s = S[K]
ans = ''

for i in S:
    if i == s:
        ans += i
    else:
        ans += '*'

print(ans)
N, M = map(int, input().split())
L, R = 1, N

import math

def merge_list(list):
    L = list[-1][0]
    R = sorted(data, key=lambda x: x[1])[-1][1]
    return (L, R)

data = []
for i in range(0, M):
    l, r = input().split()
    data.append((int(l), int(r)))
data = sorted(data, key=lambda x: x[0])

import numpy as np
def saiki(totyuu):
    D = 2 # ぶんかつすう
    if len(totyuu) < 100:
        return merge_list(list(totyuu))
    else:
        return merge_list(np.array_split(totyuu, D))

data = saiki(data)

print(max(0, data[1]-data[0]+1))

### FIXED CODE ###

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

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)
import math

X = [int(x) for x in input().split()]

v = math.gcd(X[0], X[1])
j = X[0] / v
p = int(X[1] * j)

print(p)


### FIXED CODE ###

import fractions

X = [int(x) for x in input().split()]

v = fractions.gcd(X[0], X[1])
j = X[0] / v
p = int(X[1] * j)

print(p)
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A,B,C,D= map(int,input().split())
CD=lcm(C, D)

def xc(x,C=C,D=D,CD=CD):
    return(x//C+x//D-x//(CD))

print(B-A+1-xc(B+1)+xc(A))

### FIXED CODE ###

import fractions
  
A,B,C,D= map(int,input().split())
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
CD=lcm(C, D)
 
dc =  B//C -  (A-1)//C
dd = B//D - (A-1)//D
dcd = B//CD - (A-1)//CD
 
print(B-A+1-dc-dd+dcd)
s = list(input())

for i in range(len(s)):
  if s[i] == '?':
    if s[i+1] == 'D':
      s[i] = 'P'
    elif s[i+1] == '?':
      s[i] = 'P'
      s[i+1] = 'D'
    else :
      s[i] = 'D'
      
print("".join(s))

### FIXED CODE ###

s = list(input())

for i in range(len(s)):
  if s[i] == '?':
    if i-1 >= 0 and s[i-1] == 'P':
      s[i] = 'D'
    elif i+1 < len(s) and s[i+1] == 'D':
      s[i] = 'P'
    elif i+1 < len(s) and  s[i+1] == '?':
      s[i] = 'P'
      s[i+1] = 'D'
    else :
      s[i] = 'D'
      
print("".join(s))
import math
a,b,h,m=map(int,input().split())
tyok=h*30+m*0.5
tank=m*6
sa=abs(tyok-tank)
print(math.sqrt(a**2+b**2-2*a*b*math.cos(math.radians(sa))))


### FIXED CODE ###

n=list(input())
if n[-1]=='3':
  print('bon')
elif n[-1]=='0' or n[-1]=='1' or n[-1]=='6' or n[-1]=='8':
  print("pon")
else :
  print("hon")
s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))

def is_ok(n,l):
  dp=[[0]*20001 for _ in range(len(l)+1)]
  n+=10000
  dp[0][10000]=1
  for i in range(1,len(l)+1):
    for j in range(20001):
      if j+l[i-1]<=20000:
        dp[i][j+l[i-1]]|=dp[i-1][j]
      if j-l[i-1]>=0:
        dp[i][j-l[i-1]]|=dp[i-1][j]
  if dp[len(l)][n]==1:
    return True
  else:
    return False

if is_ok(abs(x),dx) and is_ok(abs(y),dy):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))

def is_ok(n,l):
  dp=set([0])
  for d in l:
    t=[]
    for v in dp:
      t.append(v+d)
      t.append(v-d)
    dp=set(t)
  return True if n in dp else False

if is_ok(x,dx) and is_ok(y,dy):
  print("Yes")
else:
  print("No")
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
cd = [list(map(int, input().split())) for i in range(n)]

for a, b in ab:
  cost, idx = 10**18, 0
  for i, (c, d) in enumerate(cd):
    if cost > abs(a - c) + abs(b - d):
      cost = abs(a - c) + abs(b - d)
      idx = i + 1
  print(idx)


### FIXED CODE ###

n, m = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(n) :
  ai, bi = map(int, input().split())
  a.append(ai), b.append(bi)
for i in range(m) :
  ci, di = map(int, input().split())
  c.append(ci), d.append(di)

for i in range(n) :
  cost, ans = 10**18, 0
  for j in range(m) :
    if cost > abs(a[i] - c[j]) + abs(b[i] - d[j]) :
      cost = abs(a[i] - c[j]) + abs(b[i] - d[j])
      ans = j+1
  print(ans)
from itertools import groupby
inputs = open(0).readlines()

n = int(inputs[0])
*D, = map(int, inputs[1].split())
D.sort()
mod = 998244353

keys, nodes = [], [] 
for k, g in groupby(D):
    keys.append(k)
    nodes.append(len(list(g)))

if nodes[0] == 1 and all(i == k for i, k in enumerate(keys)):
    ans = 1
    for n0, n1 in zip(nodes, nodes[1:]):
        patterns.append(patterns[-1] * pow(n0, n1, mod) % mod)
        ans = ans * pow(n0, n1, mod) % mod
    print(ans)
else:
    print(0)

### FIXED CODE ###

from collections import Counter
inputs = open(0).readlines()

n = int(inputs[0])
*D, = map(int, inputs[1].split())
mod = 998244353

nbs = [0] * (max(D)+1)
for k, v in Counter(D).items():
    nbs[k] = v

if D[0] != 0 or nbs[0] != 1:
    print(0)
else:
    ans = 1
    for n0, n1 in zip(nbs, nbs[1:]):
        ans = ans * pow(n0, n1, mod) % mod
    print(ans)
x=n//(a+b)
if (a+b)*x<=a:
  t=n-x*(a+b)
else:
  t=a
print(a*x+t)

### FIXED CODE ###

n,a,b=map(int,input().split())
x=n//(a+b)
if n-(a+b)*x<=a:
  t=n-x*(a+b)
else:
  t=a
print(a*x+t)
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    A = [0] + LI()
    ans = []
    x = []
    xn = []

    def make_x(x,xn,p):
        for i in range(N+1):
            for j in range(N+1):
                if j == p:
                    x.append((A[i]*2+A[j],i,j))
                    xn.append(A[i]*2+A[j])
                else:
                    x.append((A[i]+A[j],i,j))
                    xn.append(A[i]+A[j])

        x.sort()
        xn.sort()

    for i in range(2,N+1):
        if A[i-1] > A[i]:
            y = False
            make_x(x,xn,i-1)
            j = bisect.bisect(xn,A[i]-A[i-1])
            if i > 2:
                if A[i-2] > A[i-1] + xn[j-1]:
                    y = True
            if y == False:
                if j > 0 and i == 2:
                    for k in x[j-1][1:]:
                        if k > 0:
                            ans.append((k,i-1))
                        A[i-1] += xn[j-1]
                else:
                    y = True
            if y:
                make_x(x,xn,i)
                j = bisect.bisect_left(xn,A[i-1]-A[i])
                for k in x[j][1:]:
                    if k > 0: ans.append((k,i))
                A[i] += xn[j]

    print(len(ans))
    for x in ans:
        print(x[0],x[1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    A = LI()
    ans = []

    max_a = max(A)
    min_a = min(A)

    if max_a * min_a < 0:
        p = max_a if abs(max_a) > abs(min_a) else min_a
        q = A.index(p)
        for i in range(N):
            ans.append((q+1,i+1))
            A[i] += p
        min_a = min(A)

    if min_a >= 0:
        for i in range(1,N):
            ans.append((i,i+1))
    else:
        for i in range(N,1,-1):
            ans.append((i,i-1))

    print(len(ans))
    for x in ans:
        print(x[0],x[1])

if __name__ == '__main__':
    main()
a, b, k = map(int, input().split())

ans = 0

if (a < b):
    list = [i for i in range(b+1) if (a % i == 0 && b % i == 0 && i != 0)]
    ans = list[k-1]
else:
    list = [i for i in range(a+1) if (a % i == 0 && b % i == 0 && i != 0)]
    ans = list[k-1]

print(ans)

### FIXED CODE ###

a, b, k = map(int, input().split())

ans = 0

lista = list(range(a+1))
aa = lista.pop(0)

listb = list(range(b+1))
bb = listb.pop(0)

if (a < b):
    li = [i for i in lista if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]
else:
    li = [i for i in listb if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]

print(ans)
o = input()
e = input()
counter = 0
ans = ""
while len(o) > counter:
    ans = str(ans) + o[counter] + e[counter]
    counter+=1
print(ans)

### FIXED CODE ###

o = input()
e = input()
counter = 0
ans = ""
while len(o) > counter:
    ans = str(ans) + o[counter]
    if len(o) > len(e):
        if counter == len(o)-1:
            break
    ans = ans + e[counter]
    counter+=1
print(ans)
H, N = map(int, input().split())
# AB = [list(map(int, input().split())) for _ in range(N)]

AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))


d = [0] + [10**18] * H

for hp in range(1, H + 1):
    for ab in AB:
        # print(ab)
        hp_remain = hp - ab[0]
        if hp_remain < 0: hp_remain = 0
        # print(hp_remain)
        c = d[hp_remain] + ab[1]
        if c < d[hp]: d[hp] = c

print(d[H])




### FIXED CODE ###

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

ans = 0

a, b = H // A, H % A
if b == 0:
  print(a)
else:
  print(a+1)
N = int(input())
ans = 'No'

if(N//10 == 9):
    ans = 'Yes'
if(N%0 == 9):
    ans ='Yes'

### FIXED CODE ###

N = int(input())
ans = 'No'

if(N//10 == 9):
    ans = 'Yes'
if(N%10 == 9):
    ans ='Yes'
print(ans)
if int(input()) < = 999:
  print("ABC")
else:
  print("ABD")

### FIXED CODE ###

a = int(input())
if a <= 999:
  print("ABC")
else:
  print("ABD")
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        A = [False] * N
        t = 0
        for i in range(M):
            while True:
                while A[t]:
                    t += 1
                A[t] = True
                if A[(t + i + 1)% N]:
                    A[t] = False
                    t += 1
                    continue
                break
            A[(t + i + 1) % N] = True
            print(t + 1, t + i + 2)

main()


### FIXED CODE ###

def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        s = set()
        t = 0
        for i in range(M):
            a, b = i + 1, N - i - t
            if (b - a) in s or (a + N - b) in s or b - a == a + N - b:
                t += 1
                b = N - i - t
            print(a, b)
            s.add(b - a)
            s.add(N + a - b)

main()