Harryxun/stf_run huggingface dataset:
X=int(input())
def PrimeFactor(n):
    ret=[]
    for i in range(2,int(-(-n**0.5//1))+1):
        if i!=2 and i%2==0:
            continue
        cnt=0
        while n%i==0:
            cnt+=1
            n//=i
        if cnt!=0:
            ret.append([i,cnt])
    if n!=1:
        ret.append([n,1])
    return ret
L=PrimeFactor(X)
L.append([1,1])
Y=False
ans=[]
for l in L:
    x=l[0]
    b=-1*x-1
    while True:
        tmp=(b+x)**5-b**5
        if tmp==X:
            Y=True
            ans=[b+x,b]
            break
        if tmp>X and b+x>0:
            break
        b+=1
    if Y:
        break
print(ans[0],ans[1])

### FIXED CODE ###

X=int(input())
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 divisors
L=make_divisors(X)
Y=False
ans=[]
for x in L:
    a=0
    while True:
        tmp=a**5-(a-x)**5
        if tmp==X:
            Y=True
            ans=[a,a-x]
            break
        if tmp>X and a>int(X**0.2)+1:
            break
        a+=1
        
    if Y:
        break
print(ans[0],ans[1])
N,_ = map(str,input().split())
lists = [0,1,2,3,4,5,6,7,8,9]
s=list(map(int,input().split()))
price=""
flg=False

for i in s:
    lists.remove(i)

for i in N:
    for j,n in enumerate(lists):
        if int(i) <= int(j):
            price+=str(j)
            break
        if len(lists)==n:
            price+=str(lists[0])
            flg=True
#先頭0の場合
if lists[0]==0: lists.remove(0)
#繰り上がりの場合
if flg: price=str(lists[0])+price

print(price)

### FIXED CODE ###

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

sums=0
for i in num:
	sums+=i
  
if sums ==17:
	print("YES")
else:
	print("NO")
s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][k==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]
    if s[i]!='0':dp[i][j][1]+=dp[i-1][j][0]
print(sum(dp[-1][-1]))

### FIXED CODE ###

s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][m==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]
    if s[i]!='0':dp[i][j][1]+=dp[i-1][j][0]
print(sum(dp[-1][-1]))
N, Y = map(int, input().split())
sum = 0
is_exist = False
for i in range(N+1):
  for j in range(N+1):
    k = N - i - j
    sum = i * 10000 + j * 5000 + k * 1000
    if sum == Y and i + j + k == N:
      printf("{} {} {}".format(i, j, k))
      is_exist = True
      break
  if is_exist:
    break
if is_exist == False:
  print("-1 -1 -1")

### FIXED CODE ###

def find(n, y):
  for i in range(n+1):
    for j in range(n+1-i):
      if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
        return i, j, n-i-j
  return -1, -1, -1
N, Y = map(int, input().split())
i, j, k = find(N, Y)
print("{} {} {}".format(i, j, k))
h,w=map(int,input().split())
d=[]
field=[]
fie=[]
for _ in range(h):
	s=input()
	d.append(s)
	cnt=0
	yoko=[]
	for i in range(w):
		if s[i]=="#":
			yoko.append(cnt)
			cnt=0
		else:
			cnt+=1
	if cnt>0:
		yoko.append(cnt)
	yoko.append(0)
	yoko.append(0)
	field.append(yoko)
for i in range(w):
	tate=[]
	cnt=0
	for j in range(h):
		if d[j][i]=="#":
			tate.append(cnt)
			cnt=0
		else:
			cnt+=1
	if cnt>0:
		tate.append(cnt)
	tate.append(0)
	tate.append(0)
	fie.append(tate)
for i in range(h):
	for j in range(len(field[i])-2):
		if field[i][j]>0 and field[i][j+1]>0:
			field[i].insert(j+1,0)
		elif field[i][j]>=0 and field[i][j+1]==0 and field[i][j+2]==0:
			field[i].insert(j+1,0)
for i in range(w):
	for j in range(len(fie[i])-2):
		if fie[i][j]>0 and fie[i][j+1]>0:
			fie[i].insert(j+1,0)
		elif fie[i][j]>=0 and fie[i][j+1]==0 and fie[i][j+2]==0:
			fie[i].insert(j+1,0)
ans=[[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
	k=0
	cn=0
	for j in range(w):
		if field[i][k]==0:
			k+=1
			continue
		else:
			ans[i][j]+=field[i][k]
			cn+=1
		if cn==field[i][k]:
			cn=0
			k+=1
for i in range(w):
	k=0
	cn=0
	for j in range(h):
		if fie[i][k]==0:
			k+=1
			continue
		else:
			ans[j][i]+=fie[i][k]
			cn+=1
		if cn==fie[i][k]:
			cn=0
			k+=1
M=0
for i in range(h):
	for j in range(w):
		M=max(ans[i][j],M)
print(M-1)






### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
	s.append(input().rstrip())
num=[[0]*w for _ in range(h)]
for i in range(h):
	p=0
	for j in range(w):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(h):
	p=0
	for j in range(w-1,-1,-1):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h-1,-1,-1):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
ans=0
for i in range(h):
	ans=max(ans,max(num[i])-3)
print(ans)
from fractions import gcd
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    common = lcm_list(A)
    cnt = M // common
    if (cnt + 0.5) * common <= M:
        print(cnt + 1)
    else:
        print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def cnt_div_2(x):
    cnt = 0
    while x > 0:
        if x % 2 == 0:
            x //= 2
            cnt += 1
        else:
            break
    return cnt

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    cnt_2 = cnt_div_2(A[0])
    for a in A:
        if cnt_div_2(a) != cnt_2:
            print(0)
            exit()


    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if ((2 * cnt + 1) * common) // 2 <= M:
        print(cnt + 1)
    else:
        print(cnt)
    
if __name__ == "__main__":
    main()
S=int(input())
if S="ABC":
    print("ARC")
else:
    print("ABC")







### FIXED CODE ###

S=input()
if S=="ABC":
    print("ARC")
else:
    print("ABC")
import math
A,B=map(int,input().split())
x=A*B//math.gcd(A,B)

print(x)


### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
x=(A*B)//(gcd(A,B))

print(x)
s = list(input())
t = list(input())

l = []

for i in range(len(s)-len(t) - 1):
    f = True
    for j in range(len(t)):
        if s[i+j] != '?' and s[i+j] != t[j]:
            f = False
            break
    if f:
        a = s[:i] + t + s[i+len(t):]
        l.append(a.replace('?','a'))
if len(l)>0:
    print(min(l))
else:
    print('UNRESTORABLE')


### FIXED CODE ###

s = input()
t = input()

l = []

for i in range(len(s)-len(t) + 1):
    f = True
    for j in range(len(t)):
        if s[i+j] != '?' and s[i+j] != t[j]:
            f = False
            break
    if f:
        a = s[:i] + t + s[i+len(t):]
        l.append(a.replace('?','a'))
if len(l)>0:
    print(min(l))
else:
    print('UNRESTORABLE')
def uq(a,c):
    return c if a%c==0 else uq(c,a%c)

n=(int)(input())

result = 1

for j in range(0,n):
    f=(int)(input())
    result=((result*f/uq(result,f)))
    
print((int)(result))

### FIXED CODE ###

def uq(a,c):
    return c if a%c==0 else uq(c,a%c)

n=(int)(input())

result = 1

for j in range(0,n):
    f=(int)(input())
    result=((result//uq(result,f)))*f
    
print((int)(result))
X=input()
y=int(X)
while y<1000:
  y-=1000
  z+=1
result=z*2+y*1
str_result=str(result)
print('str_result')

### FIXED CODE ###

X=input()
y=int(X)
z=0
while y>=500:
   y-=500
   z+=1
a=0
while y>=5:
    y-=5
    a+=1
   
result=z*1000+a*5
str_result=str(result)
print(str_result)
n,k = map(int,input().split())
l = list(map(int,input().split()))
for i in range(n-k+1):
  if l[i] <0 and l[i+k]<0:
    print(abs(l[i]))
  elif l[i] >0 and l[i+k]>0:
    print(abs(l[i+k]))
  elif l[i] <0 and l[i+k]>0:
    print(min(abs(l[i]),l[i+k])*2 + max(abs(l[i]),l[i+k]))

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
ls = []
for i in range(n-k+1):
  a = l[i]
  b = l[i+k-1]
  ls.append(min(abs(a)+abs(a-b), abs(b)+abs(a-b)))
print(min(ls))
n=int(input())
s=list(input())

num=2**(n-1).bit_length()
st=[set() for _ in range(2*num)]

def update1(pos,x):
  pos+=num
  st[pos].add(x)
  while pos>=0:
    pos=(pos-1)//2
    st[pos]=st[2*pos+1]|st[2*pos+2]
    
def update2(pos,x):
  pos+=num
  st[pos].discard(x)
  while pos>=0:
    pos=(pos-1)//2
    st[pos]=st[2*pos+1]|st[2*pos+2]
    st[pos].discard(x)
    
def query(l,r):
  tl=l+num
  tr=r+num
  ret=set()
  while tl<tr:
    if tr&1==1:
      tr-=1
      ret=ret|st[tr-1]
    if tl&1==1:
      ret=ret|st[tl-1]
      tl+=1
    tl=tl//2
    tr=tr//2
  return len(ret)

for i in range(n):
  update1(i,s[i])

q=int(input())
for _ in range(q):
  a,b,c=map(str,input().split())
  a=int(a)
  b=int(b)-1
  if a==1:
    if c==s[b]:
      continue
    update2(b,s[b])
    s[b-1]=c
    update1(b,c)
    print(st)
  elif a==2:
    c=int(c)-1
    print(query(b,c))

### FIXED CODE ###

def ctoi(c):
  return ord(c)-97

n=int(input())
s=list(input())

bits=[[0]*(n+1) for _ in range(26)]

def query(pos):
  ret=[0]*26
  for i in range(26):
    tmp=0
    p=pos
    while p>0:
      tmp+=bits[i][p]
      p-=p&(-p)
    ret[i]=tmp
  return ret

def update(pos,a,x):
  while pos<=n:
    bits[a][pos]+=x
    pos+=pos&(-pos)

for i in range(n):
  update(i+1,ctoi(s[i]),1)

q=int(input())
for _ in range(q):
  flag,a,b=map(str,input().split())
  flag=int(flag)
  a=int(a)
  if flag==1:
    if s[a-1]==b:
      continue
    else:
      update(a,ctoi(s[a-1]),-1)
      update(a,ctoi(b),1)
      s[a-1]=b
  elif flag==2:
    b=int(b)
    cnt1=query(b)
    cnt2=query(a-1)
    ans=0
    for i in range(26):
      if cnt1[i]-cnt2[i]>0:
        ans+=1
    print(ans)
N = int(input())
p = list(map(int,input().split()))

now = count = 0
while(now<N):
    if p[now]==now+1:
        tmp = p[now]
        p[now] = p[now+1]
        p[now+1] = tmp
        now -= 1
        count += 1
        continue
    now += 1
print(count)



### FIXED CODE ###

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

now = count = 0
while(now<N):
    if p[now]==now+1:
        if now+1 != N:
            tmp = p[now]
            p[now] = p[now+1]
            p[now+1] = tmp
            now -= 1
            count += 1
            continue
        else:
            tmp = p[now]
            p[now] = p[now-1]
            p[now-1] = tmp
            now -= 1
            count += 1
            continue
    now += 1
print(count)
N = N / 2

if N % 2 == 0:
  print(N)
  
if N % 2 != 0:
  print(N+1)
  


### FIXED CODE ###

N = int(input())
 
if N % 2 == 0:
  print(N//2)
  
if N % 2 != 0:
  print((N//2)+1)
N = int(input())
list = [int(a) for a in input().split()]

A = sum(list)//N

for i in range(-100:100):
    for j in range(N):
        sum = 0
        sum_new = 0
        sum = sum + (list[j] - A) ** 2
        sum_new = sum_new + (list[j] - i) ** 2
        if(sum > sum_new):
            sum = sum_new
print(sum)


### FIXED CODE ###


N = int(input())
list = [int(a) for a in input().split()]

A = sum(list)//N
ans = 0

for k in range(N):
    ans = ans + (list[k] - A) ** 2

for i in range(-100,100):
    sum_new = 0
    for j in range(N):
        sum_new = sum_new + (list[j] - i) ** 2
    if(ans > sum_new):
        ans = sum_new

print(ans)
while True:
    try:
        a,b = map(int,input().split())
        print(len(str(a+b)))
    except ValueError:
        break

### FIXED CODE ###

while True:
    try:
        a,b = map(int,input().split())
        print(len(str(a+b)))
    except EOFError:
        break
n = int(input())
nums = list(map(input().split(' '), lambda x: 1 / int(x)))
print(1 / sum(nums))

### FIXED CODE ###

n = int(input())
nums = map(lambda x: 1 / int(x), input().split(' '))
print(1 / sum(nums))
def main():
    n, m = map(int, input().split())
    left = 1
    right = n
    is_shift = False
    ans = []
    while left < right:
        if right - left <= n // 2 and not is_shift:
            left += 1
        ans.append([left, right])
        left += 1
        right -= 1

    for l in range(m):
        print(*ans[l])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    left = 1
    right = n
    is_shift = False
    ans = []
    while left < right:
        if right - left <= n // 2 and not is_shift and n % 2 == 0:
            left += 1
            is_shift = True
        ans.append([left, right])
        left += 1
        right -= 1

    for l in range(m):
        print(*ans[l])


if __name__ == "__main__":
    main()
cnt = 1
c = input()
while c != 0:
 print(cnt,c)
 c = input()
 cnt += 1


### FIXED CODE ###

cnt = 1
c = int(input())
while c != 0:
 print("Case {0}: {1}".format(cnt,c))
 c = int(input())
 cnt += 1
N, K = map(int, input().split())
A = list(map(int, input().split()))
teleport = dict()
for i, a in enumerate(A):
    teleport[i+1] = a
# teleport

state = 1
connect = []
looplen= 0
for n in range(K):
    connect.append(state)
    state = teleport[state] 
    if state in connect:
        looplen = n-connect.index(state)+1
        # print(connect.index(state))
        # print(n)
        break
connect
index = k%looplen
end = connect[index]
print(end)

### FIXED CODE ###

looplenn,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

loop_start = a[know[-1]]
for i,num in enumerate(know):
    if num == loop_start:
        loop_init = i
        loop = know[i:]
        break

#print(know,start,loop)

cnt = len(loop)
if k < len(know):
    ans = know[k]
else:
    ans = loop[(k-loop_init)%cnt]
# ans = loop[k%cnt]


print(ans)
#Make a Rectangle
N = int(input())
A = list(map(int, input().split())

a = sorted(A, reverse=True)
b = []

i = 0
while i<N-2:
    if ( a[i]==a[i+1] ):
        b+=[a[i]]
        i+=2
    else:
        i+=1
    if (len(b)>=2):
        break

if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])

### FIXED CODE ###

#Make a Rectangle
N = int(input())
A = list(map(int, input().split()))

a = sorted(A, reverse=True)
b = []

i = 0
while i<N-1:
    if ( a[i]==a[i+1] ):
        b+=[a[i]]
        i+=2
    else:
        i+=1
    if (len(b)>1):
        break

if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])
h=[]
h.append("P")

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

for i in range(1,n+1):
  h.append("B"+h[i-1]+"P"+h[i-1]+"B")
  #print (h[i])
  
taberu=h[n][0:x]
print(taberu.count("P"))

### FIXED CODE ###

#解答参照した
n,x=map(int,input().split(" "))

P=[1]
M=[1]

for i in range(1,n):
  P.append(2*P[i-1]+1)
  M.append(2*M[i-1]+3)
  
def F(n,x):
  if n==0:
    return 0 if x<=0 else 1
  elif x<=1:
    return 0
  elif 1<x<=M[n-1]+1:
    return F(n-1,x-1)
  elif x==M[n-1]+2:
    return P[n-1]+1
  elif M[n-1]+2<x<2*M[n-1]+3:
    return P[n-1]+1+F(n-1,x-2-M[n-1])
  elif x==2*M[n-1]+3:
    return 2*P[n-1]+1
  else:
    return P[n-1]+1+F(n-1,x-2-M[n-1])
    #print("OH!"+str(n))
    
print (F(n,x))
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
money=0
l=[]
for i in range(N):
    l.append(ab[i][0])
l.sort()
for i in range(N):
   # min_id=l.index(min(l))
    if ct+ab[i][1]<M:
        money+=ab[i][0]*ab[i][1]
        ct+=ab[i][1]
        #l[i]=10000000000
    else:
        for i in range(ab[i][1]):
            money+=l[i]
            ct+=1
            if ct==M:
                break
       # l[min_id]=100000000000
        if ct==M:
            break
print(money)


# ## 


### FIXED CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
ct1=0
ct2=0
money=0
l=[]
id=[]
for i in range(N):
    l.append(ab[i][0])
id=sorted(range(len(l)),key=lambda k: l[k])
l.sort()
while ct<M:
    while ct2<ab[id[ct1]][1]:##
        money+=l[ct1] #l[ct1]
        #print(money,l[ct1])
        ct+=1
        ct2+=1
        if ct==M:
            break
    ct1+=1
    ct2=0
print(money)
a = map(int, input().split())

for i in range(5):
    if a[i] == 0:
        print(i+1)



### FIXED CODE ###

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

for i in range(5):
    if a[i] == 0:
        print(i+1)
import math
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = math.gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = math.gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, math.gcd(gcd_l_li[target-1], gcd_r_li[target-1]))
print(ans)




### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[n-2-target]))
print(ans)
s = input()
x,y = map(int,input().split())
k = 0
data = [[],[]]
f = 0
p = 1
for s_ in s:
    if p==1 and s_=='F':
        x -= 1
        continue
    p = 0
    if s_ == 'T':
        if f:
            data[k].append(f)
        k = (k+1)%2
        f = 0
    else:
        f += 1
if f:
    data[k].append(f)

nx = sum(data[0])
ny = sum(data[1])

if nx<x or ny<y:
    print('No')
    exit()

dpx = [[0]*(nx+2)*2 for _ in range(len(data[0])+1)]
dpy = [[0]*(ny+2)*2 for _ in range(len(data[1])+1)]
x_zero = nx+1
y_zero = ny+1
dpx[0][x_zero] = 1
dpy[0][y_zero] = 1

for i in range(len(data[0])):
    for j in range(len(dpx[i])):
        if dpx[i][j]==1:
            dpx[i+1][j+data[0][i]] = 1
            dpx[i+1][j-data[0][i]] = 1

for i in range(len(data[1])):
    for j in range(len(dpy[i])):
        if dpy[i][j]==1:
            dpy[i+1][j+data[1][i]] = 1
            dpy[i+1][j-data[1][i]] = 1
if dpx[-1][x_zero+x]==1 and dpy[-1][y_zero+y]==1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

now=0
idx=-1
data=[[],[]]
cnt=0
for s in input():
    if s=='F':
        cnt+=1
    elif s=='T':
        if idx==-1:
            now+=cnt
            cnt=0
            idx=1
        elif idx==0:
            data[0].append(cnt)
            cnt=0
            idx=1
        elif idx==1:
            data[1].append(cnt)
            cnt=0
            idx=0
if idx==-1:
    now+=cnt
else:
    data[idx].append(cnt)
def solve(target,move):
    dp={0,}
    for m in move:
        dpc=dp.copy()
        dp=set()
        for k in dpc:
            dp|={k-m,k+m}
    if target in dp:
        return True
    return False
x,y=map(int,input().split())
x-=now
if solve(x,data[0]) and solve(y,data[1]):
    print('Yes')
else:
    print('No')
import sys
input = sys.stdin.buffer.readline

def main():
    H,W,D = map(int,input().split())
    a = [list(map(int,input().split())) for _ in range(H)]
    pos = [[-1,-1] for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            pos[a[i][j]-1][0] = i
            pos[a[i][j]-1][1] = j
    
    def manhattan_dist(x1,y1,x2,y2):
        return abs(x2-x1)+abs(y2-y1)

    ans_list = [[0] for _ in range(D)]
    for i in range(D):
        for j in range((H*W-i-1)//D):
            x1,y1 = pos[D*j+i]
            x2,y2 = pos[D*(j+1)+i]
            md = manhattan_dist(x1,y1,x2,y2)
            ans_list[i].append(ans_list[i][-1]+md)
    
    Q = int(input())
    for _ in range(Q):
        a,b = map(int,input().split())
        mod = (a-1)%D
        print(ans_list[mod][(b-mod)//D]-ans_list[mod][(a-mod)//D])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    H,W,D = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    Q = int(input())
    test = [list(map(int,input().split())) for _ in range(Q)]
    
    at = [None for _ in range(H*W)]
    for x in range(H):
        for y in range(W):
            at[A[x][y]-1] = (x,y)
            
    def move(x,y):
        dx = abs(at[y][0]-at[x][0])
        dy = abs(at[y][1]-at[x][1])
        return dx + dy
            
    cost = [[0 for _ in range(-(-H*W//D))] for _ in range(D)]
    for i in range(D):
        do = -(-(H*W-i)//D)
        for j in range(do-1):
            cost[i][j+1] = cost[i][j] + move(D*j+i,D*(j+1)+i)
            
    for i in range(Q):
        start,goal = test[i]
        v = start % D - 1
        u = -(-start // D) - 1
        w = -(-goal // D) - 1
        print(cost[v][w]-cost[v][u])
    
if __name__ == "__main__":
    main()
import math

a,b=[int(i) for i in input().split()]
print(math.gcd(a,b))

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

a,b=[int(i) for i in input().split()]

print(a*b//gcd(a,b))
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()

line = input_line.split(' ')
a = int(line[0])
b = int(lint[1])
c = a + b

if c > 2 and c % 3 == 0:
	print('Possible')

if a > 2 and a % 3 == 0:
	print('Possible')
	return

if b > 2 and b % 3 == 0:
	print('Possible')
	return

print('Impossible')


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()

line = input_line.split(' ')
a = int(line[0])
b = int(line[1])
c = a + b

if c > 2 and c % 3 == 0:
	print('Possible')
elif a > 2 and a % 3 == 0:
	print('Possible')
elif b > 2 and b % 3 == 0:
	print('Possible')
else:
	print('Impossible')
o = input()
e = input()

i = 0
res = []
while True:
    if o[i]:
        res.append(o[i])
    else:
        break
    if e[i]:
        res.append(e[i])
        i += 1
    else:
        break

print(''.join(res))

### FIXED CODE ###

o = input()
e = input()

lo = len(o)
le = len(e)
i = 0
res = []
while True:
    if i == len(o):
        break
    else:
        res.append(o[i])
    if i == len(e):
        break
    else:
        res.append(e[i])
        i += 1

print(''.join(res))
N, T = map(int, input().split())

dises = sorted([tuple(map(int,input().split())) for i in range(N)])

dp = [[0] * 3100 for _ in range(3100)]

for i in range(1, N + 1):
    for j in range(1, T):
#dpをもとにした最大値の更新
        dp[i][j] = dp[i-1][j] 
        ans = max(ans, dp[i][j] + dishes[i-1][1]) #最後に、最も時間のかかるものを食べて、大きい場合は最大値（ans）を更新

# dpの更新
        if j - dishes[i-1][0] >= 0: #最後に食べる品が持ち時間より長いばあいはNG
            dp[i][j] = max(dp[i][j], dp[i-1][j-dishes[i-1][0]] + dishes[i-1][1]) #ラストオーダーまでにj-dishes[i-1][0]の時間があるので

print(ans)

### FIXED CODE ###

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

dishes = sorted([tuple(map(int,input().split())) for i in range(N)])

dp = [[0] * 3100 for _ in range(3100)]
ans = 0

for i in range(1, N + 1):
    for j in range(1, T):
#dpをもとにした最大値の更新
        dp[i][j] = dp[i-1][j] 
        ans = max(ans, dp[i][j] + dishes[i-1][1]) #最後に、最も時間のかかるものを食べて、大きい場合は最大値（ans）を更新

# dpの更新
        if j - dishes[i-1][0] >= 0: #最後に食べる品が持ち時間より長いばあいはNG
            dp[i][j] = max(dp[i][j], dp[i-1][j-dishes[i-1][0]] + dishes[i-1][1]) #ラストオーダーまでにj-dishes[i-1][0]の時間があるので

print(ans)