Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	man = 0
	syu = 0
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
		if i < K:
			man += d
			if t == 1:
				syu += 1
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		for i, val in enumerate(osushi_list):
			d, t = val
			if t == 1:
				syu_local += 1
				man += d
				count += 1
				if syu_local == syu_mokuhyou or count >= K:
					break
					
		for i, val in enumerate(osushi_list):
			if count >= K:
				break
			d, t = val
			if t == 0:
				man += d
				count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	sushi_mii = []
	sushi_kii = []
	syu = [[] for i in range(N)]
	for i in range(N):
		t,d = inputMap()
		t -= 1
		syu[t].append(d)

	for i in syu:
		if len(i) > 0:
			i.sort()
			i = i[::-1]
			for j,val in enumerate(i):
				if j == 0:
					sushi_mii.append(val)
				else:
					sushi_kii.append(val)

	sushi_mii.sort()
	sushi_mii = sushi_mii[::-1]
	sushi_kii.sort()
	sushi_kii = sushi_kii[::-1]

	sushi_mi = []
	sushi_ki = []
	for i,val in enumerate(sushi_mii):
		if i == 0:
			sushi_mi.append(val)
		else:
			tmp = sushi_mi[i-1]
			sushi_mi.append(tmp + val)

	for i,val in enumerate(sushi_kii):
		if i == 0:
			sushi_ki.append(val)
		else:
			tmp = sushi_ki[i-1]
			sushi_ki.append(tmp + val)

	ans = 0
	for i in range(1, min(len(sushi_mi), K)+1):
		x = 0
		tmp = 0
		if K - i > len(sushi_ki):
			continue

		tmp += sushi_mi[i-1]
		x = i

		if K - i > 0:
			tmp += sushi_ki[K - i-1]

		oishi = tmp + x * x
		if ans < oishi:
			ans = oishi
	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

suml = [0] * (N+1)
tmp = 0
for i in range(1, N+1):
    tmp += A[i-1]
    suml[i] = tmp

ret = 0
for i in range(N+1):
    for j in range(i+1, N+1):
        if suml[j] == suml[i]:
            ret += 1

print(ret)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

suml = [0] * (N+1)
tmp = 0
for i in range(1, N+1):
    tmp += A[i-1]
    suml[i] = tmp

c = Counter(suml)
ret = 0
for i in c.values():
    if i > 1:
        ret += (i-1) * i // 2

print(ret)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
# tmp = set()
# from bisect import bisect_left
# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#         break
#     tmp.add(v)
# #     na = []
# #     ii = bisect_left(a, v*2)
# #     for 
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
ss = 0
for i in range(1, n):
    num = a[i]
    for j in range(min(len(tmp), ss+10)):
        item = tmp[j]
        if num%item==0:
            break
        if item*2>num:
            ss = j
#             print(item, num, ss)
            tmp.append(num)
            break
    else:
        tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###

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

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b
dp=[[[0]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]

for b1 in range(1,k1+k2+k3+1):
    for b2 in range(min(b1,k2+k3)+1):
        for b3 in range(min(b2,k3)+1):
            i,j,k=b1-b2,b2-b3,b3
            v=n
            if i:v+=dp[i-1][j][k]*i
            if j:v+=dp[i+1][j-1][k]*j
            if k:v+=dp[i][j+1][k-1]*k
            v/=b1
            dp[i][j][k]=v

print(dp[k1][k2][k3])

### FIXED CODE ###

n=int(input())

b=[0,0,0]
for i in map(int,input().split()):
    b[i-1]+=1
k1,k2,k3=b
dp=[[[None]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]
dp[0][0][0]=0

for k in range(k3+1):
    for j in range(k2+k3+1-k):
        for i in range(k1+k2+k3+1-j-k):
            if not i+j+k:continue
            dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)

print(dp[k1][k2][k3])
### BUGGY CODE ###

def main():
    S = input()
    result = 0
    L = len(S)
    for i in range(L-3):
        j = i + 3
        for _ in range(10**6):
            if j >= L:
                break
            if int(S[i:j+1]) % 2019 == 0:
                result += 1
                j += 3
            j += 1
    print(result)
main()

### FIXED CODE ###

def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()
### BUGGY CODE ###

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

for i in range(1,n+1):
  ans.append(str(a.index(i)+1))
  
print(" ".join(ans))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num=["0"]*n
count="1"

for i in a:
  num[i-1]=count
  count=int(count)
  count+=1
  count=str(count)
  
print(" ".join(num))
### BUGGY CODE ###

def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([n, 1])

        return arr

    n = int(input())
    a = list(map(int, input().split()))
    import copy
    gcddict = {}
    for i in range(n):
        primes = factorization(a[i])
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = factorization(a[i])
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= k **test[k]
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))

resolve()

### FIXED CODE ###

def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])
    lsd = lsd % mod

    ans = 0
    for i in range(n):
        ans += (lsd * pow(a[i], mod-2, mod)) % mod

    print(int(ans % mod))

resolve()
### BUGGY CODE ###

import collections
N = int(input())
S = {}
for i in range(N):
    value = input()
    if value in S:
        S[value] += 1
    else:
        S[value] = 1
S_sorted = sorted([k for k, v in S.items() if v == max(S.values())])
for ans in S_sorted:
    print(ans)


### FIXED CODE ###

import collections
N = int(input())
S = {}
for i in range(N):
    value = input()
    if value not in S:
        S[value] = 1
    else:
        S[value] += 1
S_largest = max(S.values())
S_sorted = sorted(S.items(), key=lambda x:x[1], reverse=True)
ans = []
for i in range(len(S_sorted)):
    if S_sorted[i][1] == S_largest:
        ans.append(S_sorted[i][0])
    else:
        break
ans_sorted = sorted(ans)
for a in ans_sorted:
    print(a)
### BUGGY CODE ###

import statistics
import numpy as np

num_q = int(input())
x = 0
f = 0
a = []
c = False

for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    a.append(n)
    x_tmp = statistics.median_low(a)
    if c:
      f += m + np.abs(x - n)
    else:
      f += m + np.abs(x_tmp - n)
    c = ~c
    x = x_tmp


### FIXED CODE ###

from heapq import heappush, heappop

num_q = int(input())
x = 0
f = 0
low = []
high = []
odd = False
num_a = 0
 
for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    if odd:
      if n >= -low[0]:
        f += m + n + low[0]
        heappush(high, n)
      else:
        f += m - n - low[0]
        heappush(low, -n)
        heappush(high, -heappop(low))
    else:
      f += m
      if num_a == 0:
        heappush(low, -n)
      else:
        if n > -low[0]:
          if n > high[0]:
            f += n - high[0]
          heappush(high, n)
          heappush(low, -heappop(high))
        else:
          f += - n - low[0]
          heappush(low, -n)

    odd = ~odd
    x = -low[0]
    num_a += 1
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]    
    for t in range(k+1,N):
      s3=S[t]
      if s1==s2:
        break
      if s3==s1 or s3==s2:
        continue
      elif t-k != k-i:
        ans+=1
print(ans)        

### FIXED CODE ###

N=int(input())
S=input()
ans=0
RGB=[0,0,0]
for i in range(N):
  if S[i]=="R":
    RGB[0]+=1
  if S[i]=="G":
    RGB[1]+=1
  if S[i]=="B":
    RGB[2]+=1
ans=RGB[0]*RGB[1]*RGB[2]    
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]
    t=k+k-i
    if s1==s2:
      continue
    if t<=N-1:
      s3=S[t]
      if s3!=s1 and s3!=s2:
        ans-=1      
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
H = [0]
H += list(map(int, input().split()))
miti = [[] for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    miti[a].append(b)
    miti[b].append(a)
kouho = [i + 1 for i in range(N)]
ans = []
while kouho != []:
    now = kouho[0]
    kouho = kouho[1::]
    flag = True
    koko = H[now]
    for i in miti[now]:
        if H[i] >= koko:
            flag = False
        elif i in kouho:
            kouho.remove(i)
    if flag == True:
        ans.append(now)
print(len(ans))


### FIXED CODE ###

N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))
kouho = set([i + 1 for i in range(N)])
hazure = set()
for i in range(M):
    a, b = map(int, input().split())
    Ha = H[a]
    Hb = H[b]
    if Ha >= Hb:
        hazure.add(b)
    if Ha <= Hb:
        hazure.add(a)
ans = kouho - hazure
print(len(ans))
### BUGGY CODE ###

# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)


### FIXED CODE ###

# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)
### BUGGY CODE ###

N, A, B = map(int, input().split(" "))


balls = []
isFinish = True
count = 0
while isFinish:
    if len(balls) >= N:
        isFinish = False
    
    for i in range(A):

        if len(balls) >= N:
            isFinish = False
            break
        balls.append('b')
        count += 1
        

    for i in range(B):
        if len(balls) >= N:
            isFinish = False
            break
        balls.append('r')
        

print(count)

### FIXED CODE ###

def main():
    N, A, B = map(int, input().split(" "))
    if (A + B) == 0:
        print(0)
        return
    amari = N % (A+B)
    kaisuu = N // (A+B)
    print(kaisuu*A+min(amari, A))
main()
### BUGGY CODE ###

# TLE: 通常の DP (もらう DP)
# dp[i] = dp[i-x]
n, k = map(int, input().split())

S = []
for _ in range(k):
    l, r = map(int, input().split())
    for s in range(l, r+1):
        S.append(s)

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S: # max n個ある！
        if i-s >= 0:
            dp[i] += dp[i-s]
            dp[i] %= MOD

print((dp[n] + MOD) % MOD)


### FIXED CODE ###

n, k = map(int, input().split())
LR = []
for _ in range(k):
    l, r = map(int, input().split())
    LR.append([l, r+1])

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[0] = 1
dp[1] = -1

for i in range(n): # i:[0,n-1]
    if i > 0: dp[i] += dp[i-1]
    for j in range(k):
        l, r = LR[j]
        if i+l < n:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r < n:
            dp[i+r] -= dp[i]
            dp[i+r] %= MOD

print((dp[n-1] + MOD) % MOD)
### BUGGY CODE ###

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

max = 0

for x in range(n+1):
    y = ((a*x)//b) - (a * (x//b))
    if y > max:
        max = y

print(max)

### FIXED CODE ###

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

x = min(b-1, n)

print((a*x)//b)
### BUGGY CODE ###

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


b_searched = set()
b_unsearched = []


b_searched.add(tuple(b))
delit = delitable(b)

if delit == []:
    print("-1")
for delit_num in delit:
    b_unsearched.append([b[:delit_num - 1] + b[delit_num:], [delit_num]])


while b_unsearched:
    b, log = b_unsearched.pop()

    b_tuple = tuple(b)
    b_searched.add(b_tuple)
    delit = delitable(b)
    if not delit:
        if not b:
            log.reverse()
            print("\n".join(map(str, log)))
            break
        else:
            continue
    for delit_num in delit:
        b_temp = b[:delit_num - 1] + b[delit_num:]
        if not tuple(b_temp) in b_searched:
            b_unsearched.append([b_temp, log + [delit_num]])
else:
    print("-1")

### FIXED CODE ###

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


log = []
while b:
    delit = delitable(b)
    if not delit:
        print(-1)
        break
    del b[delit[-1] - 1]
    log.append(delit[-1])
else:
    log.reverse()
    print("\n".join(map(str, log)))
### BUGGY CODE ###

def calcMax(i):
  now = numbers[i] 

  future_max = max(numbers[i+1:])
  #print(numbers[i+1:])
  t = numbers[i+1:]
  #print((max(t)))
  return future_max - now

n = int(input())

numbers = []
for i in range(n):
  numbers.append(int(input()))

m = -1000000001
for i in range(len(numbers) - 1):
    temp = calcMax(i)
    #print("temp: " + str(temp))
    if temp > m:
        m = temp

print (m)


### FIXED CODE ###

def calcMax(i):
  now = numbers[i]

  future_max = max(numbers[i+1:])
  #print(numbers[i+1:])
  t = numbers[i+1:]
  #print((max(t)))
  return future_max - now

n = int(input())

numbers = []
for i in range(n):
  numbers.append(int(input()))

m = -1000000001
ti = 1000000001
for i in range(len(numbers) - 1):
    if numbers[i] < ti:
      if (i == 0 or i == len(numbers) - 1 or (numbers[i-1] >= numbers[i] and numbers[i] <= numbers[i+1])):
        temp = calcMax(i)
        #print("temp: " + str(temp))
        if temp > m:
            m = temp
            ti = numbers[i]

print (m)
### BUGGY CODE ###

s = input()
T = set([0])
for i in range(len(s)):
    T.add(int(s[i::]) % 2019)

print(len(s)+1-len(T))

### FIXED CODE ###

s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))
### BUGGY CODE ###

N, M = map(int, input().split())
for i in range(M//N, 0, -1):
	if M%i == 0:
		break
print(i)


### FIXED CODE ###

N, M = map(int, input().split())
d = []
for i in range(1, int(M**0.5)+1):
	if M%i == 0:
		d.append(i)
		d.append(M//i)
d.sort()
for i in range(1,len(d)+1):
	if d[-i] <= M//N:
		print(d[-i])
		exit()
### BUGGY CODE ###

import math

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

count = 0
a.sort()

while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    b=2**math.floor(math.log2(temp))
    if a ==[]:
        break
    if 2*b-temp in a:
        count += 1
        a.pop(a.index(2*b-temp))
    
    
print(count)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)
### BUGGY CODE ###

x,y=map(int,input().split());ans=0
i=2
if x==y:
  print(-1)
else:
  while True:
    if (x*i)%y!=0:
      print(x*i)
      break
    i+=1
    

### FIXED CODE ###

x, y=map(int, input().split())
print(-1 if x%y==0 else x)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
D = [int(i) for i in input().split()]
d = set(D)
M = int(input())
T = [int(i) for i in input().split()]

dict_d = {}
for i in d:
    dict_d[i] = D.count(i)

for i in T:
    if i not in d:
        print('NO')
        exit()
    else:
        if dict_d[i] > 0:
            dict_d[i] -= 1
        else:
            print('NO')
            exit()

print('YES')


### FIXED CODE ###

from collections import Counter

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

d = Counter(D)
t = Counter(T)
d_key = list(d.keys())
t_key = list(t.keys())

p = len(d_key)
d_key += t_key
q = set(d_key)

if p != len(q):
    print('NO')
    exit()

for i in t_key:
    if t[i] > d[i]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/10000) + 1

for i in range(max1):
  rest1 = y-i*10000
  max2 = int((rest1)/5000) + 1
  for ii in range(max2):
    rest2 = y-i*10000-ii*5000
    mod = rest2%1000
    iii = int(rest2/1000)
    tot = i+ii+iii
    if(mod == 0 and tot == n):
      print(i, ii, iii)
      sys.exit()

print(-1,-1,-1)

### FIXED CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in range(max1):
  rest = y-i*9000-n*1000
  mod = rest%4000
  ii  = int((rest)/4000)
  iii = n-i-ii
  if(mod == 0 and iii>=0 and ii>=0):
    print(i, ii, iii)
    sys.exit()
    
print(-1,-1,-1)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []
L = []
for i in range(N):
    A.append(K - Q)
for i in range(Q):
    L.append(int(input()))
for i in range(Q):
    for j in range(N):
        if j == L[i] - 1:
            A[j] += 1

for i in range(N):
    if A[i] <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = []
L = []
for i in range(N):
    A.append(K - Q)
for i in range(Q):
    L.append(int(input()))
for i in range(Q):
    j = L[i]
    A[j - 1] += 1

for i in range(N):
    if A[i] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

X=int(input())

Xkon=X**0.2
if(Xkon==int(Xkon)):
    print(str(0)+" "+str(int(-Xkon)))
    #break
else:
    m=-(10**4)
    while m<0:
        A=X+(m**5)
        check=(A**0.2)
        # print(type(check))
        if(type(check)!=complex):
            if(check==int(check)):
                AnsA=-check
                AnsB=-m
                print(str(int(AnsB))+" "+str(int(AnsA)))
                break
            else:
                pass
        else:
            m=m+1
    n=1
    while n<10**4:
        A=X+(n**5)
        check=(A**0.2)
        if(check==int(check)):
            AnsA=check
            AnsB=n
            print(str(int(AnsB)+" "+str(int(-AnsA))))
            break
        else:
            n=n+1


### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break