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

N,M,Q = map(int,input().split())
Exp = [list(map(int,input().split())) for i in range(M)]
Exp.sort()
memo = [[0 for i in range(N)] for j in range(N)]
for e in Exp:
    for i in range(e[0]):
        for j in range(N-e[1]+1):
            memo[i][e[1]+j-1] += 1
Query = [list(map(int,input().split())) for i in range(Q)]
for q in Query:
    print(memo[q[0]-1][q[1]-1])

### FIXED CODE ###

N,M,Q = map(int,input().split())
memo = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l][r] += 1
for i in range(N):
    for j in range(N):
        memo[i+1][j+1] += memo[i][j+1] + memo[i+1][j] - memo[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
### BUGGY CODE ###

from collections import Counter

N = int(input())
listA = list(map(int,input().split()))
listA_hozon = listA

S = Counter(listA)
#print(S)

##key##
key = S.keys()
#for i in key:
#  print(i)

for i in listA:
  out = 0
  listA = listA_hozon
  for a in key:
    if a == i:
      num = S[a]-1
      add = (S[a]-1) * (S[a]-2) /2
      out = out + add
    else:
      num = S[a]
      add = S[a] * (S[a]-1) /2
      out = out +add
  print(int(out))

### FIXED CODE ###

from collections import Counter

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

S = Counter(listA)

##key##
key = S.keys()
out = 0
for i in key:
  out = out + S[i] * (S[i]-1) /2

for i in listA:
  test = out - S[i] * (S[i]-1) /2 + (S[i] -1) * (S[i]-2) /2
  print(int(test))
### BUGGY CODE ###

def cmb_mod_p(n, r, mod): # nCr mod p

    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    return g1[n] * g2[r] * g2[n-r] % mod

n, k = map(int, input().split())
a = list( map(int, input().split()))
MOD = 10**9 + 7
ans = 0

a.sort()

for j in range(n):
    i = j +1
    if j <= n-k:
        minX = a[i-1]
        ans -= a[i-1]*cmb_mod_p(n-i,k-1,MOD)%MOD
    if k -1 <= i:
        maxX = a[i-1]
        ans += a[i-1]*cmb_mod_p(i-1,k-1,MOD)%MOD

print(ans%MOD)


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

ans = 0


a.sort()

for j in range(n):
    i = j +1
    if j <= n-k:
        minX = a[i-1]
        ans -= a[i-1]*cmb(n-i,k-1,mod)%mod
    if k -1 <= i:
        maxX = a[i-1]
        ans += a[i-1]*cmb(i-1,k-1,mod)%mod

print(ans%mod)
### BUGGY CODE ###

from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1) #pow(a,b)==a^b べき乗
    a[i] %= mod
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)

### FIXED CODE ###

from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1,mod) #pow(a,b)==a^b べき乗
    
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import deque

def main(): 
    H,W = map(int,input().split())
    S = [input().split() for _ in range(H)]
    for i in range(H):
        S[i]=list(S[i][0])
    grid = [[0]*W for _ in range(H)]
    
    for i in range(H):
        l=0
        for j in range(W):
            if S[i][j] == "#":
                for k in range(1,l+1):
                    grid[i][j-k]+=l
                l=0
            else:
                l+=1
        for k in range(1,l+1):
                    grid[i][W-k]+=l
    max=0
    for j in range(W):
        l=0
        for i in range(H):
            if S[i][j] == "#":
                for k in range(1,l+1):
                    grid[i-k][j]+=l
                    if grid[i-k][j] > max:
                        max = grid[i-k][j]
                l=0
            else:
                l+=1
        for k in range(1,l+1):
            grid[H-k][j]+=l
            if grid[H-k][j] > max:
                        max = grid[H-k][j]
    print(max-1)
if __name__ == "__main__":
    main()
    

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

def main(): 
    H,W = map(int,input().split())
    S = [input().split() for _ in range(H)]
    for i in range(H):
        S[i]=list(S[i][0])
    grid = [[0]*W for _ in range(H)]
    
    for i in range(H):
        l=0
        for j in range(W):
            if S[i][j] == "#":
                for k in range(1,l+1):
                    grid[i][j-k]+=l
                l=0
            else:
                l+=1
        for k in range(1,l+1):
                    grid[i][W-k]+=l
    max=0
    for j in range(W):
        l=0
        for i in range(H):
            if S[i][j] == "#":
                for k in range(1,l+1):
                    grid[i-k][j]+=l
                    if grid[i-k][j] > max:
                        max = grid[i-k][j]
                l=0
            else:
                l+=1
        for k in range(1,l+1):
            grid[H-k][j]+=l
            if grid[H-k][j] > max:
                        max = grid[H-k][j]
    print(max-1)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,q = map(int, input().split())
str = input()
for i in range(q):
  l,r = map(int, input().split())
  sub_str = str[(l-1):r]
  print(sub_str.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

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

L = [0 for i in range(max(A) + 1)]

for a in A:
    L[a] += 1
    if a != 0:
        L[a - 1] += 1
    if a != max(A):
        L[a + 1] += 1

print(max(L))




### FIXED CODE ###

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

L = [0 for i in range(max(A) + 10)]

for a in A:
    L[a] += 1
    L[a - 1] += 1
    L[a + 1] += 1

print(max(L))
### BUGGY CODE ###

from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(r):
        ans*=(n-i)
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x[i]=a%2019
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    ans += combi(cc[i][1],2)

print(ans)


### FIXED CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

print(ans)
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(1,N+1):
    p = p*i
print(p%(10**9+7))

### FIXED CODE ###

import math
N = int(input())
p = math.factorial(N)
print(int(p%(10**9+7)))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!
#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans

#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))


#逆元を使うと容易に頑張れるｃ
def conbination(n,a,mod=10**9+7):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
#操作から作れるものの組み合わせは何個かー＞同じものでも違う方法で構成できるかから考える方法もある
#入力

def pin(type=int):
    return map(type,input().rstrip().split())
    
def resolve():
    N,=pin()
    A=list(pin())
    S=[sum(A[:i])for i in range(N+1)]
    from collections import Counter
    s=list(Counter(S).values())
    ans=0
    for j in s:
        if j>1:
            ans+=conbination(j,2)
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """6
1 3 -4 2 2 -2"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7
1 -1 1 -1 1 -1 1"""
        output = """12"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
1 -2 3 -4 5"""
        output = """0"""
        self.assertIO(input, output)
if __name__=="__main__":resolve()

### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!

#入力

def pin(type=int):
    return map(type,input().rstrip().split())
from collections import Counter
from itertools import accumulate as acm
def resolve():
    N,=pin()
    S=list(acm(pin()))
    S.insert(0,0)
    s=list(Counter(S).values())
    ans=0
    for j in s:
            ans+=(j*(j-1))//2
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
if __name__=="__main__":resolve()
### BUGGY CODE ###

from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[int(x) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
for k in data:
    A=A+([k[1]]*k[0])


ans = sum(sorted(A)[::-1][:N])
print(ans)

### FIXED CODE ###

from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[(int(x),1) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    r,q=[int(x) for x in stdin.readline().rstrip().split()]
    A.append((q,r))
ans=0
cnt=0
for j in reversed(sorted(A)):
    cnt+=j[1]
    ans+=(j[0]*j[1])
    if cnt > N:
        ans = ans-(j[0]*(cnt-N))
        break
print(ans)
### BUGGY CODE ###

from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = -1

# def chk(a):
#     for i in range(N-1):
#         if a[i] > a[i+1]:
#             return False
#     return True

def cnt(idx):
    res = 0
    for i in range(N):
        res += abs(idx[i] - i)
    return res // 2

for idx in permutations(range(N)):
    # print(idx)
    a = []
    flg = True
    for i in range(N):
        if (idx[i] % 2) ^ (i%2):
            a.append(B[idx[i]])
        else:
            a.append(A[idx[i]])
        if i and (a[i-1] > a[i]):
            flg = False
            break
    # print(a)
    if flg:
        if ans == -1:
            ans = cnt(idx)
        else:
            ans = min(ans, cnt(idx))

print(ans)

### FIXED CODE ###

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

v = [[0, 0] for _ in range(N)]
s = []
ans = 500

for i in range(1<<N):
    tmp = 0
    for j in range(N):
        if ((i>>j)&1): v[j] = [B[j], j]
        else:          v[j] = [A[j], j]
    for j in range(N):
        p = j
        while (p and v[p][0] < v[p-1][0]):
            v[p], v[p-1] = v[p-1], v[p]
            tmp += 1
            p -= 1
    for j in range(N):
        if (((i>>v[j][1])+v[j][1]-j)&1):
            s.append(v[j][0]*500+j)
    if (len(s)&1):
        tmp = 500
        s.pop()
    while s:
        p = s.pop()
        q = s.pop()
        if ((p-q)&1): tmp += p-q
        else:         tmp += 500
    ans = min(ans, tmp)

if ans < 500:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions,time
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

st = time.time()
n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); quit()
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
    if now == zan or time.time() - st > 1700:
        print(-1)
        quit()

            


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions,time
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

st = time.time()
n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); quit()
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
        nnn = time.time()
    if now == zan:
        print(-1)
        quit()
    if nnn - st > 1.7:
        print(n*(n-1)//2)
        quit()
### BUGGY CODE ###

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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1
dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    i1 = i - 1
    for j in range(-(i // 2), i + 1):
        tmp = dp[i - 3][j] * i12
        tmp += dp[i - 2][j + 1] * i1
        tmp += dp[i - 1][j - 1]
        dp[i][j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)


### FIXED CODE ###

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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)
### BUGGY CODE ###

import sys

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

mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	h,w=map(int,input().split())
	AB=np.array(read().split(), np.int64)
	
	
	A=AB[:h*w]
	B=AB[h*w:]
	
	A=np.reshape(A, (h,w))
	B = np.reshape(B, (h, w))
	
	G=abs(A-B)
	M=(h+w)*80

	
	li=[[[10**9]*M for i in range(w)] for j in range(h)]

	
	li[0][0][G[0][0]]=G[0][0]
	for i in range(h):
		for j in range(w):
			for k in range(M):

				if li[i][j][k]!=10**9:

					try:
						li[i + 1][j][abs(k - G[i][j])] = abs(k - G[i][j])
						li[i + 1][j][abs(k + G[i][j])] = abs(k + G[i][j])
					except:
						pass
					try:
						li[i][j + 1][abs(k - G[i][j])] = abs(k - G[i][j])
						li[i][j + 1][abs(k + G[i][j])] = abs(k + G[i][j])
					except:
						pass
	
	
	print(min(li[h-1][w-1])-1)
	
			
			
			
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	h, w = map(int, input().split())
	
	G = [[0] * w for i in range(h)]
	A = [0]*h
	B = [0]*h
	
	for i in range(h):
		A[i] = list(map(int, input().split()))
	for i in range(h):
		B[i] = list(map(int, input().split()))
	
	for i in range(h):
		for j in range(w):
			G[i][j]=abs(A[i][j]-B[i][j])

	M = (h + w) * 80

	li = [[[0] * M for i in range(w)] for j in range(h)]
	
	li[0][0][G[0][0]] = 1
	for i in range(h):
		for j in range(w):
			for k in range(M):
				
				if li[i][j][k] == 1:
					if i < h - 1:
						li[i + 1][j][abs(k - G[i+1][j])] = 1
						li[i + 1][j][abs(k + G[i+1][j])] = 1
					if j < w - 1:
						li[i][j + 1][abs(k - G[i][j+1])] = 1
						li[i][j + 1][abs(k + G[i][j+1])] = 1

	for i in range(M):
		if li[h-1][w - 1][i] == 1:
			print(i)
			exit(0)


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

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

_sum = 0
for i in range(len(As) - 1):
    _sum += As[i+1] * sum(As[0:i+1])

print(_sum % (10**9 + 7))


### FIXED CODE ###

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

_sum = 0
x = 0
for i in range(len(As) - 1):
    _sum += As[i+1] * (x + As[i])
    x += As[i]

print(_sum % (10**9 + 7))
### BUGGY CODE ###

# B - Frog 2
def main():
    N, K, *H = map(int, open(0).read().split())
    H = [0] + H + [0] * K
    dp = [1 << 30] * (N + K + 1)
    dp[1] = 0
    for i, a in enumerate(H[1:N + 1], 1):
        for j, b in enumerate(H[i + 1:i + K + 1], i + 1):
            dp[j] = min(dp[j], dp[i] + abs(a - b))
    print(dp[N])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# EduDPB - Frog 2
import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, a, b = MAP()
h = [INT() for _ in range(n)]
ad = a - b
l = 1
r = 10 ** 9
while r - l > 10:
    c = (r + l) // 2
    cnt = 0
    for i in range(n):
        cnt += (max(h[i] - b * c, 0) + ad - 1) // ad
    if c > cnt:
        r = c
    else:
        l = c
ans = inf
for i in range(max(0, l - 100), r + 100):
    cnt = 0
    for j in range(n):
        cnt += (max(h[j] - b * i, 0) + ad - 1) // ad
    ans = min(ans, max(i, cnt))
print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, a, b = MAP()
h = [INT() for _ in range(n)]
ad = a - b
l = 1
r = 10 ** 9
while r - l > 1:
    c = (r + l) // 2
    cnt = 0
    for i in range(n):
        cnt += (max(h[i] - b * c, 0) + ad - 1) // ad
    if c > cnt:
        r = c
    else:
        l = c
ans = inf
for i in range(l, r + 1):
    cnt = 0
    for j in range(n):
        cnt += (max(h[j] - b * i, 0) + ad - 1) // ad
    ans = min(ans, max(i, cnt))
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

cnt = 0
for i in range(q):
    query = input().split()
    if query[0] == '1':
        cnt += 1
    else:
        if query[1] == '1':
            if cnt % 2 == 0:
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if cnt % 2 == 0:
                s = s + query[2]
            else:
                s = query[2] + s

if cnt % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

s = input()
q = int(input())

t = ''
for i in range(q):
    query = input().split()
    if query[0] == '1':
        s,t = t,s
    else:
        if query[1] == '1':
            t += query[2] 
        else:
            s += query[2]

print(t[::-1] + s)
### BUGGY CODE ###

import itertools
N, M = map(int, input().split())
cakes = []
for _ in range(N):
    x, y, z = map(int, input().split())
    cakes.append((x, y, z))

ans = 0
for i in itertools.combinations(cakes, M):
    sx, sy, sz = 0, 0, 0
    for j in i:
        x, y, z = j
        sx += x
        sy += y
        sz += z
    ans = max(ans, abs(sx) + abs(sy) + abs(sz))
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
cakes = []
for _ in range(N):
    x, y, z = map(int, input().split())
    cakes.append((x, y, z))

ans = 0
for i in range(2**3):
    op1, op2, op3 = 1, 1, 1
    for idx, j in enumerate(bin(i)[2:][::-1], 1):
        j = int(j)
        if idx == 1:
            op1 = 1 if j == 0 else -1
        elif idx == 2:
            op2 = 1 if j == 0 else -1
        elif idx == 3:
            op3 = 1 if j == 0 else -1
            
    cakes.sort(reverse=True, key=lambda x: op1 * x[0] + op2 * x[1] + op3 * x[2])
    sx, sy, sz = 0, 0, 0
    for cake in cakes[:M]:
        sx += cake[0]
        sy += cake[1]
        sz += cake[2]
    ans = max(ans, abs(sx) + abs(sy) + abs(sz))
print(ans)
### BUGGY CODE ###

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

N=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)
    return divisors

def func(a,b):
    return a**5-b**5

L=make_divisors(N)

for yakusu in L:
    for a in range(N):
        b=a-yakusu
        ret=func(a,b)
        if ret==N:
            print a,b
            quit()


### FIXED CODE ###

N=input()
for a in range(-200,200):
    for b in range(-200,200):
        if a**5-b**5==N:
            print a,b
            quit()