Harryxun/stf_run huggingface dataset:
from sys import stdin, stdout
import math,sys
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
import bisect as bi
import heapq 

'''
#------------------PYPY FAst I/o--------------------------------#
 
def I():return (int(stdin.readline()))
def In():return(map(int,stdin.readline().split()))
'''
#------------------Sublime--------------------------------------#
 
sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
def I():return (int(input()))
def In():return(map(int,input().split()))



def main():
    try:
        a=list(input())
        b=list(input())
        temp=b.pop()
        if a==b:
            print('Yes')
        else:
            print('No')
    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    for _ in range(1):
        main()

### FIXED CODE ###

from sys import stdin, stdout
import math,sys
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
import bisect as bi
import heapq 

'''
#------------------PYPY FAst I/o--------------------------------#
 
def I():return (int(stdin.readline()))
def In():return(map(int,stdin.readline().split()))
'''
#------------------Sublime--------------------------------------#
 
#sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
def I():return (int(input()))
def In():return(map(int,input().split()))



def main():
    try:
        a=list(input())
        b=list(input())
        temp=b.pop()
        if a==b:
            print('Yes')
        else:
            print('No')
    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    for _ in range(1):
        main()
a,b=map(int,input().split())
if a*b%2==0:
  print(Even)
else:
  print(Odd)

### FIXED CODE ###

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

if a*b%2==0:
    print("Even")
else:
    print("Odd")
n,k = map(int,input().split())

d = abs(n-k)

print(n % d)

### FIXED CODE ###

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

if(n%k == 0):
        
    g = n//k
        
    print(n - (g*k))
else:
    g = n//k
    ans = n - (g*k)
    if(abs(ans - k) < ans):
        print(abs(ans - k))
    else:
        print(ans)
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    """
    O(N^2)dpでも行けるそうです。以下写経：
    https://atcoder.jp/contests/abc078/submissions/14886969
    dpテーブルが訳分からなくなったら@lru_cache使うのが楽。
    """
    #@lru_cache(maxsize=None)
    def dfs(turn, top, x, y): # turn: 0 => x, 1 => y
        if top == N: return abs(x - y)
        if turn == 1:
            """
            yのターンは、top以降を取ってなるべくスコアが低くなるようなiを選ぶ
            """
            ret = 10**9
            for i in range(top, N): ret = min(ret, dfs(0, i + 1, x, A[i]))
            return ret
        else:
            """
            xのターンは、top以降を取ってなるべくスコアが高くなるようなiを選ぶ
            """
            ret = 0
            for i in range(top, N): ret = max(ret, dfs(1, i + 1, A[i], y))
            return ret
    
    print(dfs(0, 0, Z, W))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, z, w = map(int, input().split())
    A = list(map(int, input().split()))
    """
    dpかと思ってずっとウンウン唸ってたのに、解説見て唖然。。。
    """
    if N == 1: print(abs(A[0] - w))
    else: print(max(abs(A[-1] - w), abs(A[-1] - A[-2])))


if __name__ == "__main__":
    main()
import sys

H, W = sys.stdin.readline().split()
C = set(map(int, sys.stdin))
for i in C:
    print(i)
    print(i)


### FIXED CODE ###

import sys

H, W = sys.stdin.readline().split()
C = map(str, sys.stdin)
for i in C:
    print(i)
    print(i)
N=int(input())
A=list(map(int,input().split()))
even=0
for i in range(N):
  if A[i]%2==0: even+=1

print(3**N-2**even)

### FIXED CODE ###

S=str(input())
for i in range(len(S)-1):
  if S[i]=="A" and S[i+1]=="C":
    print("Yes")
    break
else: print("No")
import math
p=[]
d=[i+1for i in range(1,10**5)]
while 1:
    t=d[0]
    if math.sqrt(10**5)<=t:
        p+=d
        break
    p.append(t)
    d=[e for e in d if e%t]
n,m=map(int,input().split())
a=1
while m>1:
    t=p.pop(0)
    if m%t:
        continue
    c=0
    while not m%t:
        m//=t
        c+=1
    a=a*math.factorial(n+c-1)//(math.factorial(n-1)*math.factorial(c))%(10**9+7)
print(a)

### FIXED CODE ###

import math
import random
from scipy.misc import comb
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n,m=map(int,input().split())
a=1
for c in Prime().find_factors(m).values():
    a=a*comb(n+c-1,c,exact=1)%(10**9+7)
print(a)
def f(y,x,c0):
  global A
  c=A[y][x]
  if x==0 or x==W+1 or y==0 or y==H+1: return 0
  if c=="X" or c!=c0:
    return 0
  else:
    A[y][x]="X"
    for i,j in [[0,-1],[0,1],[-1,0],[1,0]]:
      f(y+i,x+j,c0)
    return 1

while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[["X" for _ in range(W+2)] for _ in range(H+2)]
  for i in range(H):
    s=raw_input()
    for j in range(W): A[i+1][j+1]=s[j]
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      c+=f(i,j,A[i][j])
  print c

### FIXED CODE ###

def f(y,x,a):
  M.append([y,x])
  while M:
    y,x=M.pop()
    if A[y][x]==a:
      A[y][x]=' '
      for i,j in [[0,-1],[-1,0],[0,1],[1,0]]: M.append([y+i,x+j])
  return 1

M=[]
while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[list(' '*(W+2)) for _ in range(H+2)]
  for i in range(H): A[i+1][1:W+1]=list(raw_input())
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      a=A[i][j]
      if a!=' ': c+=f(i,j,a)
  print c
n = int(input())
al = []
count = 1
for i in range(n):
  a = input()
  if a　in al:
    count += 1
  else:
    al.append(a)
print(count)

### FIXED CODE ###

s = set(open(0))
print(len(s)-1)
a,b,c=input().split()
ans=a.upper[0]+b.upper[0]+c.upper[0]
print(ans)


### FIXED CODE ###

a,b,c=input().split()
ans=a.upper()[0]+b.upper()[0]+c.upper()[0]
print(ans)
s=input()
li=list(s)

i=0
j=len(s)-1
answer=0

while i!=j:
    if li[i]==li[j]:
        i+=1
        j-=1
    else:
        if li[i]!="x" and li[j]!="x":
            answer=-1
            break
        elif li[i]=="x" and li[j]!="x":
            answer+=1
            i+=1
        elif li[i]!="x" and li[j]=="x":
            answer+=1
            j-=1

print(answer)


### FIXED CODE ###

s=input()
li=list(s)

i=0
j=len(s)-1
answer=0

while i<j:
    if li[i]==li[j]:
        i+=1
        j-=1
    else:
        if li[i]!="x" and li[j]!="x":
            answer=-1
            break
        elif li[i]=="x" and li[j]!="x":
            answer+=1
            i+=1
        elif li[i]!="x" and li[j]=="x":
            answer+=1
            j-=1

print(answer)
S = input()
lead = S[0]
sub = S[2:-1]
C = sub.count('C')
if lead == 'A' and C == 1:
  for x,i in enumerate(1,len(S)):
    if i =='C' and ( 2<= x < len(S)-2):
      pass
    else:
      if i.islower():
        pass
      else:
        print('WA')
        exit()
  print('AC')
  exit()
else:
  print('WA')

### FIXED CODE ###

S = input()
lead = S[0]
sub = S[2:-1]
C = sub.count('C')
if lead == 'A' and C == 1:
  for x in range(1,len(S)):
    if S[x].islower() or S[x] == 'C':
      pass
    else:
      print('WA')
      exit()
  print('AC')
else:
  print('WA')
n,m=map(int,input().split())
line=[tuple(map(int,input().split()))for i in range(m)]
ans=[]
for i in range(m):
    ans.append(line[i][0])
    ans.append(line[i][1])
from collections import Counter
data=Counter(ans)
data=sorted(data.items())
for i in range(n):
    print(data[i][1])

### FIXED CODE ###

n,m=map(int,input().split())
line=[tuple(map(int,input().split()))for i in range(m)]
ans=[0]*n
for i in range(m):
    ans[line[i][0]-1]+=1
    ans[line[i][1]-1]+=1
for i in ans:
    print(i)
a,b,c=map(int,input().split())
def turn(n):
  global a,b,c
  def t(n,a):
    if n==a:return 0
    elif n<a:return a-n
    else:return (a-n+1)//2
  return t(n,a)+t(n,b)+(t,c)
mi=turn(0)
for i in range(1,51):mi=min(turn(i),mi)
print(mi)

### FIXED CODE ###

a,b,c=sorted(map(int,input().split()))
co=(b-a)//2
if (b-a)%2==1:co+=1;c+=1
co+=c-b
print(co)
a = map(str,input())
b = a + 1
i = 0
while i < b:
    c = a[i]
    if c == 7:
        print('yes')
        break
    elif c==a:
          print('no')
        
    i += 1


### FIXED CODE ###

a = input()
if '7' in a:
   print('Yes')
else:
   print('No')
n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

N = n
# 早いnCrの準備ここから
fact = [0] * (N+1)
fact_inv = [0] * (N+1)
inv = [0] * (N+1)

fact[0] = fact[1]  = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD # //で良いのかな?
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def combo(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % MOD) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)


### FIXED CODE ###

n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)
import sys
sys.setrecursionlimit(200000000)

def comb(n, k, mod=10**9+7):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

a1,b1,a2,b2=map(int,input().split())
score=comb(a2+b2+2,a2+1)-comb(a2+b1+1,a2+1)-comb(a1+b2+1,a1)+comb(a1+b1,a1)
print(score%(10**9+7))

### FIXED CODE ###

a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = max(a2+1,b2+1)
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(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

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))
import math
r = input()
S = r * r * math.pi
l = 2 * math.pi * r
print("{0:.5f}".format(S, l))

### FIXED CODE ###

import math
r = float(input(""))
S = r * r * math.pi
l = 2 * math.pi * r
print("{0:.5f} {1:.5f}".format(S, l))
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

    dp = np.zeros([N+1, W+1], np.int64)

    for w, v in WV:
        np.maximum(dp[1:, w:], dp[:-1, :-w] + v, out=dp[1:, w:])

    print(np.max(dp[:, W]))


main()

### FIXED CODE ###

import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])
    UV = np.sum(WV[:, 1])
    UW = np.sum(WV[:, 0])

    dp = np.full([UV+1], UW*2, np.int64)
    dp[0] = 0

    for w, v in WV:
        p_dp = dp.copy()
        np.minimum(dp[v:], p_dp[:-v] + w, out=dp[v:])

    print(max(list(np.where(dp <= W)[0])))


main()
import math
n, x, y = map(int,input().split())
num = [0 for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        num[min([j-i,math.fabs(j-y)+1+math.fabs(i-x)] += 1

for i in range(n):
    print(num[i])


### FIXED CODE ###

n, x, y = map(int,input().split())
num = [0 for i in range(n)]

for i in range(1,n+1):
    for j in range(i+1,n+1):
        ban = min([j-i,abs(x-i)+1+abs(y-j)])
        num[ban] += 1

for i in range(1,n):
    print(num[i])
a, b = map(int,input().split())
if a * b % 2 == 0:
  print("Even")
elif
  print("Odd")

### FIXED CODE ###

a, b = map(int,input().split())
if (a * b) % 2 == 0:
  print("Even")
else:
  print("Odd")
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))

S = [A[0] % k]
for i in range(1, n):
    S.append((A[i]+S[-1]) % k)

# print(S)

D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    
    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            # print(i, j, D[key1])
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(len(S)-k, len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        # print(i, j, D[key1])
    except:
        ans += 0
# print(D)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))

S = [A[0] % k]
for i in range(1, n):
    S.append((A[i]+S[-1]) % k)

# print(S)

D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            # print(i, j, D[key1])
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(max(0, len(S)-k), len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        # print(i, j, D[key1])
    except:
        ans += 0
# print(D)
print(ans)
l=list(input())
print(l.translate(str.maketrans({"1":"9", "9":"1"})))



### FIXED CODE ###

n=input()
print(1110-int(n))
s = input()
ans=0

R = 'R'*i
for i in range(1,4):
  R = 'R'*i
  if R in s:
    ans = i
    
print(ans)

### FIXED CODE ###

s = input()
ans = 0

for i in range(1, 4):
    p = "R" * i
    if p in s:
        ans = i

print(ans)
S = input()
L = [i for i in range(97,123)]
n = len(S)
for i in range(n):
    L.remove(ord(S[i]))
if n <= 25:
    X = L[0]
    ans = S + chr(X)d
else:
    T = []
    x = S[-1]
    T.append(x)
    for i in range(2,27):
        y = S[-i]
        if y > x:
            x = y
            T.append(y)
        else:
            break
    m = 26 - len(T)
    if m != 0:
        ans = S[0]
        for i in range(1,m-1):
            ans += S[i]
        for t in T:
            if t > S[m-1]:
                ans += t
                break
    else:
        ans = -1
print(ans)


### FIXED CODE ###

S = input()
L = [i for i in range(97,123)]
n = len(S)
for i in range(n):
    L.remove(ord(S[i]))
if n <= 25:
    X = L[0]
    ans = S + chr(X)
else:
    T = []
    x = S[-1]
    T.append(x)
    for i in range(2,27):
        y = S[-i]
        if y > x:
            x = y
            T.append(y)
        else:
            break
    m = 26 - len(T)
    if m > 1:
        ans = S[0]
        for i in range(1,m-1):
            ans += S[i]
        for t in T:
            if t > S[m-1]:
                ans += t
                break
    elif m == 0:
        ans = -1
    else:
        for t in T:
            if t > S[m-1]:
                ans = t
                break
print(ans)
n=int(input())
dat=list(map(int, input().split()))
      
re = 0
flag=True
while (flag==True):
        for e in dat:
            if (e%2==1): 
                 flag=False
                 break

         re = re+1

print(re)

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
import sys
n=int(input())
a=list(map(int,input().split()))
x=0
for i in range(n-1):
  if(a[i+1-x]==a[i-x]):
    a.pop(i)
    n-=1
    x+=1
    if(n==3):break
if(a[0]==a[1]):
  a.pop(0)
  n-=1

if(n==2):
  print(1)
  sys.exit()
til=a[1]-a[0]
x=0
for i in range(n-1):
  tilt=a[i+1]-a[i]
  if(til*tilt<0):
    x+=1
    if(i+2>=n):
      break
    til=a[i+2]-a[i+1]
print(x+1)

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
x=0
if(n==1):
  print(1)
  sys.exit()
for i in range(n-1):
  if(a[i+1-x]==a[i-x]):
    a.pop(i-x)
    n-=1
    x+=1
    if(n==3):break
if(a[0]==a[1]):
  a.pop(0)
  n-=1
if(n==2):
  print(1)
  sys.exit()
til=a[1]-a[0]
x=0
for i in range(n-1):
  tilt=a[i+1]-a[i]
  if(til*tilt<0):
    x+=1
    if(i+2>=n):
      break
    til=a[i+2]-a[i+1]
print(x+1)
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for i in range(q)]
m=[0]*(n+1)
for i in range(len(s)):
    
    if s[i]=='A' and s[i+1]=='C':
        m[i+1]=m[i]+1
    else:
        m[i+1]=m[i]

print(m)
for i in l:
    print(m[i[1]-1]-m[i[0]-1])

### FIXED CODE ###

#122-C
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for i in range(q)]
m=[0]*(n+1)
for i in range(len(s)-1):
    
    if s[i]=='A' and s[i+1]=='C':
        m[i+1]=m[i]+1
    else:
        m[i+1]=m[i]

for i in l:
    print(m[i[1]-1]-m[i[0]-1])
# coding: utf-8

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

if A == B && B == C:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

# coding: utf-8

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

if A == B and B == C:
  print('Yes')
else:
  print('No')
n=int(input())
XY=[]
for i in range(n):
  XY.append([int(i) for i in input().split()])
ans=0
def dis(X):
  return (X[0]**2+X[1]**2)**0.5
for i in range(n):
  A=[dis(XY[i])]
  x1,y1=XY[i][0],XY[i][1]
  for j in range(n):
    if j==i:
      continue
    else:
      x2,y2=XY[j][0],XY[j][1]
      A.append((x1*x2+y1*y2)/A[0])
  ans1,ans2=0,0
  for k in range(n):
    if A[k]>=0:
      ans1+=A[k]
    else:
      ans2-=A[k]
  ans=max([ans,ans1,ans2])
print(ans)



### FIXED CODE ###

import math
n=int(input())
def f(x,y):
  return math.atan2(y,x)
  
XY=[]
for i in range(n):
  x,y=map(int,input().split())
  XY.append((x,y,f(x,y)))
XY.sort(key=lambda x:x[2])

def dis(x,y):
  return (x**2+y**2)**0.5
ans=0
for i in range(n):
  for j in range(1,n+1):
    x,y=0,0
    if i+j<=n:
      for k in range(i,i+j):
        x+=XY[k][0]
        y+=XY[k][1]
      ans=max(ans,dis(x,y))
    else:
      for k in range(i,n):
        x+=XY[k][0]
        y+=XY[k][1]
      for k in range(j-(n-i)):
        x+=XY[k][0]
        y+=XY[k][1]
      ans=max(ans,dis(x,y))
print(ans)
n,k= map(int,input().split())
from math import factorial 
for i in range(1,k+1):
  if n-k+1 >= i:
    print(int(((factorial(k-1)) * (factorial(n-k+1))/(factorial(i-1))/(factorial(k-i))/(factorial(i))/(factorial(n-k+1-i)))%(10**9+7)))
  else:
    print(0)

### FIXED CODE ###

import math
MOD = 10 ** 9 + 7

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


def f(n):
    return math.factorial(n)


for i in range(K):
    if N - K - i >= 0:
        print(f(N - K + 1) // f(N - K - i) // f(i + 1)
              * (f(K - 1) // f(K - i - 1) // f(i)) % MOD)
    else:
        print(0)
inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, AB[i][0]):
            T[i][j] = T[i-1][j]
        for j in range(AB[i][0], H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[-1][-1])

### FIXED CODE ###

inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, min(AB[i][0], H+1)):
            T[i][j] = min(T[i-1][j], AB[i][1])
        for j in range(AB[i][0], H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[N-1][H])
while True:
	a,b=sort(map(int(input())))
	break if a==0 and b==0
	print(a,b)


### FIXED CODE ###

while True:
	a,b=map(int,input().split())
	if (a==0) and (b==0):
		break
	if a > b :
		a,b = b,a
	print(a,b)