Harryxun/stf_run huggingface dataset:
from itertools import *
from bisect import *
from operator import *

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

a_item = sorted(a)
a_max = a_item[-1]
#a_item = a_item[:-1]
bisect_l_item = bisect_left(a_item, a_max//2)
#import pdb; pdb.set_trace()
bisect_l = a_item[bisect_l_item]
bisect_r = a_item[bisect_l_item - 1]
#print(bisect_l_item, bisect_l, bisect_r)
idea_l = len(list(combinations(range(a_max), bisect_l)))
idea_r = len(list(combinations(range(a_max), bisect_r)))

if idea_l >= idea_r:
    print(a_max, bisect_l)
else:
    print(a_max, bisect_r)


### FIXED CODE ###

from itertools import *
from bisect import *
from operator import *
import math

def comb(n, r):
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r))

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

a_item = sorted(a)
a_max = a_item[-1]
a_item = a_item[:-1]
bisect_l_item = bisect_left(a_item, a_max//2)
#import pdb; pdb.set_trace()
if bisect_l_item >= n - 1:
    bisect_l = a_item[bisect_l_item - 1]
else:
    bisect_l = a_item[bisect_l_item]

bisect_r = a_item[bisect_l_item - 1]
if abs(bisect_r - a_max/2) <= abs(bisect_l - a_max/2):
    print(a_max, bisect_r)
else:
    print(a_max, bisect_l)
#print(bisect_l_item, bisect_l, bisect_r)
#idea_l = comb(a_max, bisect_l)
#idea_r = comb(a_max, bisect_r)
def main():
    N, C, K = map(int, input().split())
    T = [int(input()) for _ in range(N)]
    ans = 0
    i = 0
    j = 0
    T.sort()
    if len(T) == 1:
        ans = 1
        return(ans)

    while True:
        if T[j] + K >= T[i+1]:
            i = i + 1
            if i == N-1:
                ans += 1
                return (ans)
            for h in range(C-2):
                if T[j] + K >= T[i+1]:
                    if h == C-3:
                        ans += 1
                        i += 2
                        j = i
                        if j >= N-1:
                            return(ans)
                        break
                    else:
                        i += 1
                        if (i+1) == N-1:
                            ans += 1
                            return(ans)  
                        continue
                elif T[j] + K < T[i + 1]:
                    j = i + 1
                    i = i + 1
                    ans += 1
                    if j == N-1:
                        ans += 1
                        return(ans)
                    break

        elif T[j] + K < T[i+1]:
            ans += 1
            i += 1
            j = i
            if j == N-1:
                ans += 1
                return(ans)

print(main())



### FIXED CODE ###

def main():
    N, C, K = map(int, input().split())
    T = list(int(input()) for _ in range(N))

    T.sort()

    ans = 0
    temp = T[0]
    cnt = 1

    for i in range(1,N):
        if temp + K < T[i] or C == cnt:
            ans += 1
            temp = T[i]
            cnt = 1
        else:
            cnt += 1

    ans += 1
    return (ans)

print(main())
#人の回答を写経したもの
dic = {k: list(input()) for k in "abc"}

while dic[s]:
  s=dic[s].pop(0)

print(s.upper())

### FIXED CODE ###


#他人の答えの写経
dic = {k: list(input()) for k in "abc"}

s ="a"

while dic[s]:
  s=dic[s].pop(0)

print(s.upper())
n, m = map(int, input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]
for i in a:
  for j in b:
    if j not in i:
      print("No")
      exit()
print("Yes")


### FIXED CODE ###

a, b = map(int, input().split())
if a == 1:
  a = 14
if b == 1:
  b = 14
if a > b:
  print("Alice")
elif a < b:
  print("Bob")
else:
  print("Draw")
a,b,c=map(int(input().split()))
if a+b+c>=22:
  print("bust")
else:
  print("win")

### FIXED CODE ###

a1,a2,a3=map(int,input().split())
if a1+a2+a3>=22:
  print("bust")
else:
  print("win")
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 10)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import collections
from functools import lru_cache

xy = []
d = collections.defaultdict(list)
@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    sys.setrecursionlimit(10 ** 5 + 1)
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()
N=int(input())
S=input()
K=int(input())
for i in range(N):
  if S[K-1]==S[i]:
    S[i]='*'
print(S)

### FIXED CODE ###

input()
S=input()
k=int(input())
for s in S:print(s if s==S[k-1] else "*",end="")
from collections import deque

def main():
  N,M=map(int,input().split())
  r=[[]for i in range(M)]
  d,p=[10**6]*N,[10**6]*N

  for i in range(M):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)

  q=deque([0])
  p[0],d[0]=-1,0

  while len(q)!=0:
    i=q.pop()
    for j in r[i]:
      if d[j]>d[i]+1:
        d[j],p[j]=d[i]+1,i
        q.append(j)

  print('Yes')
  for i in range(1,N):
    print(p[i]+1)

main()


### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  r=[[]for i in range(N)]
  for i in range(M):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)

  p=[-1]*N
  q=[0]
  while q:
    i=q.pop(0)
    for j in r[i]:
      if p[j]==-1:
        p[j]=i
        q.append(j)

  print('Yes')
  for i in range(1,N):
    print(p[i]+1)

main()
# -*- coding: utf-8 -*-

class Point_Class():
    def __init__(self, x, y):
        self.x = x
        self.y = y

def slope(p1, p2):
    return (p2.y-p1.y)/(p2.x-p1.x)

n = int(raw_input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, raw_input().split())
    p1 = Point_Class(x1, y1)
    p2 = Point_Class(x2, y2)
    p3 = Point_Class(x3, y3)
    p4 = Point_Class(x4, y4)
    print "YES" if slope(p1, p2) == slope(p3, p4) else "NO"

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(raw_input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, raw_input().split())
    print "YES" if abs(((y2-y1)*(x4-x3) - (x2-x1)*(y4-y3))) < 1e-10 else "NO"
N = int(input())
A = list(map(int, input().split()))
answer = 1
 
for i in range(N):
    answer = answer*A[i]
 
if answer>10**18:
    print(-1)
else:
    print(answer)

### FIXED CODE ###

a, b = map(int, input().split())
answer = a*b
print(answer)
n = int(input())
s = str(input())
if int(ord(s)) + n > 122:
    print(chr(int(ord(s)) + n - 26))
else:
    print(chr(int(ord(s)) + n))

### FIXED CODE ###

n = int(input())
s = str(input())
ans = ''
for i in s:
    t = (int(ord(i) + n - 64)) % 26
    if t == 0:
        ans += 'Z'
    else:
        ans += chr(t + 64)
print(ans)
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()

ans=0
ikeru=[0 for i in range(n)]
for i in range(n):
    a=U(i) % p
    if a==0:ans+=1
    ikeru[a]+=1

for t in ikeru:
    if t in [0,1]:continue
    ans+= t*(t-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
n,p=map(int,input().split())
A=list(map(int,input()))
def U(x):
    return int(A[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(A[i])%p==0:
            ans+=keta
    print(ans)
    exit()
    
acc = [0 for i in range(n)] 
cur = A[-1] % p
acc[-1] = cur
k = 1
for i in range(n-2, -1, -1):
    cur += pow(10, k, p) * A[i]
    cur %= p
    acc[i] = cur
    k += 1
acc = acc + [0]
 
C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)
s=intput()
ss=intput()
for i range(len(s)):
  if(s[i]!=ss[i]):
    c+=1
print(c)

### FIXED CODE ###

n=input()
nn=input()
c=0
for i in range(len(n)):
    if(n[i]!=nn[i]):
        c+=1
print(c)
n,q=map(int,input().split())
edge=[[] for i in range(n)]
cost=[0]*n
for i in range(n):
  p,s=map(int,input().split())
  p-=1;s-=1
  edge[p].append(s)
for i in range(q):
  x,c=map(int,input().split())
  x-=1
  cost[x]+=c
for i in range(n):
  for j in edge[i]:
    cost[j]+=cost[i]
for i in cost:
  i=str(i)
print(" ".join(cost))

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
edge=[[] for i in range(n)]
cost=[0]*n
for i in range(n-1):
  p,s=map(int,input().split())
  p-=1;s-=1
  edge[p].append(s)
  edge[s].append(p)
for i in range(q):
  x,c=map(int,input().split())
  x-=1
  cost[x]+=c
visited=[False]*n
queue=deque([0])
visited[0]=True
while len(queue)!=0:
  a=queue.popleft()
  for i in edge[a]:
    if visited[i]==True:continue
    queue.append(i)
    visited[i]=True
    cost[i]+=cost[a]
for i in range(n):
  cost[i]=str(cost[i])
print(" ".join(cost))
import sys
import math
import functools

N = int(sys.stdin.readline().rstrip())
T = []
for _ in range(N):
    T.append(int(sys.stdin.readline().rstrip()))

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)

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

if N == 1:
    print(T[0])
else:
    print(lcm_list(T))

### FIXED CODE ###

import sys
import fractions
import functools

N = int(sys.stdin.readline().rstrip())
T = []
for _ in range(N):
    T.append(int(sys.stdin.readline().rstrip()))

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)

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

if N == 1:
    print(T[0])
else:
    print(lcm_list(T))
a=map(int,input().split());
print(max(a)-min(a))

### FIXED CODE ###

a=list(map(int,input().split()));print(max(a)-min(a))
N = int(input())
a = list(map(int, input().split()))
a_dict = Counter(a)
keys = a_dict.keys()
max_count = 0
for key in keys:
	tmp_count = 0
	for i in keys:
		if key + 1 == i or key - 1 == i or key == i:
			tmp_count += a_dict[i]
	if tmp_count > max_count:
		max_count = tmp_count
print(max_count)

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


if __name__ == "__main__":
    main()
inputa = input().split()

inputb = input()


a = int(inputa[0])
b = int(inputa[1])
# c = int(input[2])

inputList = list(inputb)

inputList[b] = inputList[b-1].lower()

ans = "".join(inputList)

print(ans)

# inputList.sort()
#
# list = [a+b, b+c ,c+a]
#
# ans = min(list)
# print(ans)



# flg = 1
# for i in range(0, len(inputList)-1):
#     if inputList[i] == inputList[i + 1]:
#         flg = 0
#         break
#
# if flg == 0:
#     print("Bad")
# else:
#     print("Good")


### FIXED CODE ###


inputa = input().split()

inputb = input()


a = int(inputa[0])
b = int(inputa[1])
# c = int(input[2])

inputList = list(inputb)

inputList[b-1] = inputList[b-1].lower()

ans = "".join(inputList)

print(ans)

# inputList.sort()
#
# list = [a+b, b+c ,c+a]
#
# ans = min(list)
# print(ans)



# flg = 1
# for i in range(0, len(inputList)-1):
#     if inputList[i] == inputList[i + 1]:
#         flg = 0
#         break
#
# if flg == 0:
#     print("Bad")
# else:
#     print("Good")
import sys
from math import sqrt, floor

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def main():
    a, b, n = MI()

    if b - 1 <= n:
        print((a * (b - 1)) // b)
    else:
        print((a * n) // b)) #- (a * (n // b)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt, floor

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def main():
    a, b, n = MI()

    if b - 1 <= n:
        print((a * (b - 1)) // b - (a * ((b - 1) // b)))
    else:
        print((a * n) // b - (a * (n // b)))


if __name__ == "__main__":
    main()
h,w = map(int,input().split())
Array = [list(map(str,input())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=str(num)
    
for i in Array:
  print(i)

### FIXED CODE ###

h,w = map(int,input().split())
Array = [list(map(str,input())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]=='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=str(num)
    
for i in Array:
  print(*i, sep='')
S=list(input())
flag=0
Ccount=0
Lcount=0
if S[0]=="A":
  flag+=1
  del S[0]
N=len(S)
for i in range(1,N-1):
  if S[i]=="C":
    Ccount+=1
    del S[i]
if Ccount==1:
  flag+=1
M=len(S)
for i in range(M):
  if S[i].islower():
    Lcount+=1
if Lcount==M:
  flag+=1
if flag==3:
  print("AC")
else:
  print("WA")

### FIXED CODE ###

S=list(input())
flag=0
Ccount=0
Cnumber=0
if S[0]=="A":
  flag+=1
if S[2:-1].count("C")==1:
  flag+=1
  del S[0]
  S.remove("C")
if str(S).islower():
  flag+=1
if flag==3:
  print("AC")
else:
  print("WA")
N, X = [int(nx) for nx in input().split()]
x = [abs(int(xx) - X) for xx in input().split()]

while len(x) > 1:
  x2 = []
  mn_x = min(x)
  for n in range(N):
    mod = x[n] % mn_x
    if mod != 0:
      x2.append(mod)
  x2.append(mn_x)
  x = x2
  
ans = x[0]
print(ans)

### FIXED CODE ###

N, X = [int(nx) for nx in input().split()]
x = [abs(int(xx) - X) for xx in input().split()]

while len(x) > 1:
  x2 = []
  mn_x = min(x)
  for n in range(len(x)):
    mod = x[n] % mn_x
    if mod != 0:
      x2.append(mod)
  x2.append(mn_x)
  x = x2
  
ans = x[0]
print(ans)
# solution 3
import heapq
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
s = set()
heapq.heappush(Q, (-A[0]-B[0]-C[0], 0, 0, 0))
for n in range(K):
    q, i, j, k = heapq.heappop(Q)
    print(-q)
    if i < X-1 and [i+1, j, k] not in s:
            heapq.heappush(Q, (- A[i+1] - B[j] - C[k], i+1, j, k))
            s.add((i + 1, j, k))
    if j < Y-1 and [i, j+1, k] not in s:
            heapq.heappush(Q, (- A[i] - B[j+1] - C[k], i, j+1, k))
            s.add((i, j + 1, k))
    if k < Z-1 and [i, j, k+1] not in s:
            heapq.heappush(Q, (- A[i] - B[j] - C[k+1], i, j, k+1))
            s.add((i, j, k + 1))

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
heapq.heappush(Q, (-A[0]-B[0]-C[0], 0, 0, 0))
for n in range(K):
    ans = heapq.heappop(Q)
    print(-ans[0])
    i, j, k = ans[1], ans[2], ans[3]
    if i < X-1:
        if (- A[i+1] - B[j] - C[k], i+1, j, k) not in Q:
            heapq.heappush(Q, (- A[i+1] - B[j] - C[k], i+1, j, k))
    if j < Y-1:
        if (- A[i] - B[j+1] - C[k], i, j+1, k) not in Q:
            heapq.heappush(Q, (- A[i] - B[j+1] - C[k], i, j+1, k))
    if k < Z-1:
        if (- A[i] - B[j] - C[k+1], i, j, k+1) not in Q:
            heapq.heappush(Q, (- A[i] - B[j] - C[k+1], i, j, k+1))
N, M = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(N+1)]
rank = [0] * (N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        #親を検索
        par[x] = find(par[x])
        return par[x]

def same_checker(x, y):
    return find(x) == find(y)

def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)
    print(par)
S = {}
for i in range(N):
    S[p[i]] = par[i+1]
ans = 0
for i in range(N):
    if same_checker(S[p[i]], S[i+1]):
        ans += 1

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(N+1)]
rank = [0] * (N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        #親を検索
        par[x] = find(par[x])
        return par[x]

def same_checker(x, y):
    return find(x) == find(y)

def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)
S = {}
for i in range(N):
    S[p[i]] = par[i+1]
ans = 0
for i in range(N):
    if same_checker(S[p[i]], S[i+1]):
        ans += 1

print(ans)
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [str(i) for i in input().split()]
    
    count = 0

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


### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [str(i) for i in input().split()]

    count = 0

    for  i in a[0]:
        if "2" == i:
            count +=1
    print(count)
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n = int(input())
q = [int(x) for x in input().split()]
ans = [None for _ in range(n)]
ans[0] = 0

# Top down
def dp(i):
	if i < 0: return 0
	else:
		if ans[i] != None: return ans[i]

		if i-1 >= 0: t1 = ans[i-1] + abs(q[i-1] - q[i])
		if i-2 >= 0: t2 = ans[i-2] + abs(q[i-2] - q[i])
		ans[i] = min(t1, t2)
		
		return ans[i]

dp(n-1)

# Bottom up
# for i in range(1, n):
# 	t1 = t2 = int(1e9)
# 	if i-1 >= 0: t1 = ans[i-1] + abs(q[i-1] - q[i])
# 	if i-2 >= 0: t2 = ans[i-2] + abs(q[i-2] - q[i])
# 	ans[i] = min(t1, t2)

print(ans[n-1])


### FIXED CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n = int(input())
q = [int(x) for x in input().split()]
ans = [None for _ in range(n)]
ans[0] = 0

# # Top down
# def dp(current):
# 	if ans[current] != None: return ans[current]

# 	if current < 0: return 0
# 	else:
# 		t1 = t2 = int(1e9)
# 		if current-1 >= 0: t1 = abs(q[current] - q[current-1]) + dp(current-1)
# 		if current-2 >= 0: t2 = abs(q[current] - q[current-2]) + dp(current-2)

# 		ans[current] = min(t1, t2)
# 		return ans[current]

# dp(n-1)

for i in range(1, n):
	t1 = t2 = int(1e9)
	if i-1 >= 0: t1 = ans[i-1] + abs(q[i-1] - q[i])
	if i-2 >= 0: t2 = ans[i-2] + abs(q[i-2] - q[i])
	ans[i] = min(t1, t2)
# print(ans)
print(ans[n-1])
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(max(dp)))


### FIXED CODE ###

from collections import *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    c=d.copy()
    for p,q in c.items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))
from collections import defaultdict

MOD = (10 ** 9) + 7

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

n = int(raw_input())

ns = []
d = defaultdict(int)

for i in xrange(n):
    a, b = map(int, raw_input().split())
    s = 1 if a * b >= 0 else -1
    g = gcd(abs(a), abs(b))

    m1 = (s * abs(a) / g, abs(b) / g)
    m2 = (-s * abs(b) / g, abs(a) / g)
    d[m1] += 1
    d[m2] += 0

pre = 1
for k in d.keys():
    if k[0] < 0:
        continue
    elif k[0] == 0:
        pre = pre * d[k] % MOD
    else:
        k1 = k
        k2 = (-k[1], k[0])

        tot = pow(2, d[k1], MOD) + pow(2, d[k2], MOD) - 1
        pre = pre * tot % MOD
print (pre - 1 + MOD) % MOD


### FIXED CODE ###

from collections import defaultdict

MOD = (10 ** 9) + 7
assert MOD == 1000000007

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

n = int(raw_input())

ns = []
d = defaultdict(int)
zero = 0

for i in xrange(n):
    a, b = map(int, raw_input().split())
    ns.append((a, b))
    if a and b:
        s = 1 if a * b >= 0 else -1
        g = gcd(abs(a), abs(b))
        m1 = (s * abs(a) / g, abs(b) / g)
        m2 = (-s * abs(b) / g, abs(a) / g)
    elif a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        m1 = (1, 0)
        m2 = (0, 1)
    elif b == 0:
        m1 = (0, 1)
        m2 = (1, 0)

    d[m1] += 1
    d[m2] += 0

'''
res = 0
for i in xrange(1 << n):
    fs = []
    flag = True
    for j in xrange(n):
        if i & (1 << j):
            fs.append(ns[j])
    for i, f1 in enumerate(fs):
        for f2 in fs[i + 1:]:
            (a1, b1) = f1
            (a2, b2) = f2
            if a1 * a2 + b1 * b2 == 0:
                flag = False
                break
        if not flag:
            break
    if flag:
        res += 1
print res - 1
'''

pre = 1
for k in d.keys():
    if k[0] <= 0:
        assert (k[1], -k[0]) in d
        continue
    else:
        k1 = k
        k2 = (-k[1], k[0])

        tot = pow(2, d[k1], MOD) + pow(2, d[k2], MOD) - 1
        pre = pre * tot % MOD
print (pre - 1 + zero + MOD) % MOD
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
j=n-1
s=0
for i in range(k):
    a[j]=0
    j=j-1
for i in range(n):
    s=s+a[i]
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
j=n-1
s=0
for i in range(k):
    a[j]=0
    j=j-1
    if(j<0):
        break
for i in range(n):
    s=s+a[i]
print(s)
import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))


import numpy as np


t= min(k, 45)
from numba.decorators import jit

@jit
def imos(a, n):
    bn = [0]*n
    for i in range(n):
        bn[max(i - a[i], 0)] += 1

        if i+ a[i]+1 <n:
            bn[i+a[i]+1] -=1
    return np.cumsum(bn)


for k in range(t):
    an = imos(an, n)


print(*an)

### FIXED CODE ###

s= str(input())

print(s[:3])