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

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

def readInts():
  return [int(s) for s in input().split(" ")]

def root(groups, n):
  while groups[n] != n:
    n = groups[n]
  return n

def union(groups, x, y):
  rx = root(groups, x)
  ry = root(groups, y)
  if rx != ry:
    groups[ry] = rx

def main():
  N, M = readInts()
  groups = [i for i in range(N)]

  for i in range(M):
    X, Y, Z = readInts()
    union(groups, X-1, Y-1)

  knowns = set()
  for n in range(N):
    knowns.add(root(groups, n))
  print(len(knowns))

if __name__ == "__main__":
  main()


### FIXED CODE ###

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

def readInts():
  return [int(s) for s in input().split(" ")]

def root(groups, n):
  i = n
  while groups[i] != i:
    i = groups[i]
  groups[n] = i
  return i

def union(groups, x, y):
  rx = root(groups, x)
  ry = root(groups, y)
  if rx != ry:
    groups[ry] = rx

def main():
  N, M = readInts()
  groups = [i for i in range(N)]

  for i in range(M):
    X, Y, Z = readInts()
    union(groups, X-1, Y-1)

  knowns = set()
  for n in range(N):
    knowns.add(root(groups, n))
  print(len(knowns))

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

from collections import Counter, deque

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

ca, cb = Counter(A), Counter(B)

cab = ca+cb

if any(c > N for c in cab.values()):
    print('No')
else:
    print('Yes')
    B.reverse()
    res = []
    while A:
        if A[0] != B[0]:
            A.popleft()
            res.append(str(B.popleft()))
        else:
            B.rotate()
        
    print(' '.join(res))

### FIXED CODE ###

from collections import Counter, deque

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

ca, cb = Counter(A), Counter(B)

cab = ca+cb

if any(c > N for c in cab.values()):
    print('No')
else:
    print('Yes')
    B.rotate(N//2)
    res = []
    while A:
        if A[0] != B[0]:
            A.popleft()
            res.append(str(B.popleft()))
        else:
            B.rotate()
        
    print(' '.join(res))
### BUGGY CODE ###

import sys
import numpy as np

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

B = []
for i in range(N-K+1):
    s = 1
    for j in range(K):
        s *= A[i+j]
    B.append(s)

for i in range(N-K):
    if B[i] < B[i+1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
import numpy as np
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

B = 0
s = 1
for i, a in enumerate(A):
    if i >= K:
        B = A[i-K]
        s = a
        if B != 0 and B < s:
            print('Yes')
        elif B != 0 and B >= s:
            print('No')
### BUGGY CODE ###

N,K=map(int,input().split())
h=[0]*N
s=[0]*K
d=[0]*(N-K+1)

for i in range(N):
  h[i]=int(input())
h=sorted(h)

for i in range(N-K+1):
  for j in range(K):
    s[j]=h[i+j]
  d[i]=s[K-1]-s[0]

print(min(d))

### FIXED CODE ###

N,K=map(int,input().split())
H=[int(input()) for i in range(N)]
H.sort()

ans=float('inf')
for i in range(N-K+1):
  ans=min(ans,H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
s = input()
ar = [[0 for i in range(3)] for j in range(1000)]
kakunin = [0 for i in range(1000)]
index = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            ar[index][0] = i
            ar[index][1] = j
            ar[index][2] = k
            index += 1



for i in range(n):
    # print(s[i])
    for j in range(1000):
        if kakunin[j] < 3 and ar[j][kakunin[j]] ==int(s[i]):

            kakunin[j] += 1

res = 0
for i in range(1000):
    if kakunin[i] == 3:
        res +=1
print(res)


### FIXED CODE ###

import numpy as np

n = int(input())
s = input()
ar = [[0 for i in range(3)] for j in range(1000)]
kakunin = [0 for i in range(1000)]
index = 0
res = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            a = s.find(str(i))

            if a == -1:
                continue

            b = s[a+1:len(s)].find(str(j))
            if b == -1:
                continue
            c = s[a+b+2:len(s)].find(str(k))
            if c != -1:
                # print(str(a) + "  "+ str(b) + "  " + str(c))
                # print(str(i) + "  " + str(j) + "   "+ str(k))
                # print()
                res += 1
print(res)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 'YES' 
for i in range(N):
    if A.count(A[i]) > 1:
        ans = 'NO'
        break
print(ans)


### FIXED CODE ###

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

ans = 'YES'

for i in range(N-1):
    if A[i] == A[i+1]:
        ans = 'NO'
        break
print(ans)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
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

cnt=0
ans=0
LCM=1
for i in range(n):
    Q=lcm(LCM,A[i])
    cnt*=Q//LCM
    LCM=Q
    cnt+=Q//A[i]
print(cnt%mod)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
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

cnt=0
ans=0
LCM=1
for i in range(n):
    Q=lcm(LCM,A[i])
    cnt*=Q//LCM
    LCM=Q
    cnt+=Q//A[i]
print(cnt%mod)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    heappush(heap, (0, s))
    while heap:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]:
            continue
        dist[v] = d
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V1, V2 = list(range(1, n+1)), list(range(1, n+1))
E1, E2 = defaultdict(dict), defaultdict(dict)
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V1, E1, s)
dist_snook = dijkstra(V2, E2, t)
temp = float('inf')
for i in reversed(range(n)):
    temp = min(temp, dist_yen[i+1] + dist_snook[i+1])
    ans[i] -= temp
print(*ans, sep='\n')

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(range(1, n+1))
E1, E2 = {v: {} for v in V}, {v: {} for v in V}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V, E1, s)
dist_snuuk = dijkstra(V, E2, t)
temp = float('inf')
for v in V[::-1]:
    temp = min(temp, dist_yen[v] + dist_snuuk[v])
    ans[v-1] -= temp
print(*ans, sep='\n')
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
if len(list(set(a)))<=k:
  print(0)
else:
  l=[0]*n
  for i in range(n):
    l[a[i]-1]+=1
  l.sort()
  ans=0
  cnt=0
  i=0
  while cnt<(len(list(set(a)))-k):
    if l[i]!=0:
      ans+=l[i]
      cnt+=1
      i+=1
    else:
      i+=1
  print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
if len(list(set(a)))<=k:
  print(0)
else:
  d={}
  for i in range(n):
    if a[i] in d:
      d[a[i]]+=1
    else:
      d[a[i]]=1
  d=sorted(d.items(),key=lambda x:x[1])
  m=len(d)
  cnt=0
  for i in range((len(list(set(a))))-k):
    cnt+=d[i][1]
  print(cnt)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = []
for i in input().split():
	a.append(int(i))
b = []
for i in input().split():
	b.append(int(i))
c = []
for i in input().split():
	c.append(int(i))

#a.reverse()
#b.reverse()
#c.reverse()

a_bsum = []

for i in range(x):
	for j in range(y):
			a_bsum.append(a[i]+b[j])
a_bsum.sort()
a_bsum.reverse()

temp_sum = a_bsum[0:k]

sum = []

c.sort()
c.reverse()
c = c[0:k]

for i in a_bsum:
	for j in c:
		sum.append(i+j)

sum.sort()
sum.reverse()

for i in range(k):
	print(sum[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = []
for i in input().split():
	a.append(int(i))
b = []
for i in input().split():
	b.append(int(i))
c = []
for i in input().split():
	c.append(int(i))

#a.reverse()
#b.reverse()
#c.reverse()

a_bsum = []

for i in range(x):
	for j in range(y):
			a_bsum.append(a[i]+b[j])
a_bsum.sort()
a_bsum.reverse()

a_bsum = a_bsum[0:k]

sum = []

c.sort()
c.reverse()
c = c[0:k]

for i in a_bsum:
	for j in c:
		sum.append(i+j)

sum.sort()
sum.reverse()

for i in range(k):
	print(sum[i])
### BUGGY CODE ###

S = input()
Q = int(input())

cnt = 0
for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        cnt += 1
    else:
        if (query[1] == "1" and cnt%2==0) or (query[1] == "2" and cnt%2==1):
            S = query[2]+S
        else:
            S = S+query[2]
if cnt%2 == 1:
    S = S[::-1]
print(S)

### FIXED CODE ###

s = input()
q = int(input())
list1 = []
list2 = []
flag = 1
for i in range(q):
    in_line = input().split()
    if in_line[0] == "1":
        flag *= -1
    else:
        if in_line[1] == "1":
            if flag == 1:
                list1.append(in_line[2])
            else:
                list2.append(in_line[2])
        else:
            if flag == 1:
                list2.append(in_line[2])
            else:
                list1.append(in_line[2])
if flag == 1:
    print("".join(list1[::-1]) + s + "".join(list2))
else:
    print("".join(list2[::-1]) + s[::-1] + "".join(list1))
### BUGGY CODE ###

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

L = [1]

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    for j in L:
        if i%j==0 and j!=1: 
            break
    else:
        if G%i==0: 
            L.append(i)

print(len(L))   


### FIXED CODE ###

from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)
### BUGGY CODE ###

import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
    else:
        donecp = copy.copy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

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

n = int(input())
a = list(map(int, input().split()))
mod_a = [i%(10**9 + 7) for i in a]
res = 0
for i in range(0, len(a)-1):
  for j in range(i+1, len(a)):
    res += (mod_a[i]*mod_a[j])
print(res%(10**9 + 7))
                       



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
#mod_a = [i%(10**9 + 7) for i in a]
res = 0
sum_a = sum(a)
b = 0
t = 0
for i in range(0, len(a)-1):
  t = a[i]
  b += a[i]
  res += (sum_a - b)*t%(10**9 + 7)
print(res%(10**9 + 7))
### BUGGY CODE ###

K = int(input())
Q = [1,2,3,4,5,6,7,8,9]
for i in range(K):
    x = Q.pop(0)
    if x%10!=0:
        Q.append(10*x + x%10 - 1)
    Q.append(10*x + x%10)
    if x%10!=9:
        Q.append(10*x + x%10 + 1)
print(x)

### FIXED CODE ###

from collections import deque
K = int(input())
Q = deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    x = Q.popleft()
    if x%10!=0:
        Q.append(10*x + x%10 - 1)
    Q.append(10*x + x%10)
    if x%10!=9:
        Q.append(10*x + x%10 + 1)
print(x)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
ans = []
def calc(n):
    return n-1
for i in range(n):
  ans.append(k)
for i in range(q):
  ans = list(map(calc, ans))
  ans[a[i]-1]+= 1

for i in range(n):
  if ans[i] <= 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
ans = []
def calc(n):
    return n-q
for i in range(n):
  ans.append(k)
ans = list(map(calc, ans))
for i in range(q):
  ans[a[i]-1]+= 1
for i in range(n):
  if ans[i] <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
lis = list(map(int, input().split()))
a = n // 2
res = sum(lis)


def dams(i, a, lis):
    su = 0
    for j in range(a):
        b = (i + (2 * j + 1)) % len(lis)
        su += lis[b]
    return su


ans = []
for i in range(n):
    ans.append(res - 2 * dams(i, a, lis))
print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
lis = list(map(int, input().split()))
res = sum(lis)
su = [0] * n

for i in range(n):
    if i < 2:
        su[i] = lis[i]
    else:
        su[i] = su[i-2] + lis[i]

ans = []
ans_a = ans.append

for i in range(n):
    if i == 0:
        b = su[-2]
        ans_a(res-2*b)
    elif i == 1:
        b = su[-1] - su[i-1]
        ans_a(res-2*b)
    elif i == n:
        b = su[-1] - lis[-1]
        ans_a(res-2*b)
    elif i % 2 == 0:
        b = su[-2] - su[i-1] + su[i-2]
        ans_a(res-2*b)
    else:
        b = su[-1] - su[i-1] + su[i-2]
        ans_a(res-2*b)
print(*ans)
### BUGGY CODE ###

def main():
    import numpy as np
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP = np.array([[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)], dtype = np.int64)
    DP[0, 0, 0] = 1

    for i in range(N):
        DP[i + 1, :, :] = DP[i, :, :] 
        DP[i + 1, 0, 1] = DP[i, 0, 0] + DP[i, 0, 1]
        a = A[i]
        if a > S:
            DP[i + 1, 1:, 1] = DP[i, 1:, 1] #以前から合計jになっている場合のみOK
        else:
            DP[i + 1, 1:a, 1] = DP[i, 1:a, 1] #以前から合計jになっている場合のみOK
            DP[i + 1, a: S + 1, 1] = (DP[i, a: S + 1, 1] + DP[i, :S - a + 1, 0] + DP[i, :S - a + 1, 1]) % MOD
            
        DP[i + 1, S, 2] = (DP[i, S, 1] + DP[i, S, 2])
        if a <= S:
            DP[i + 1, S, 2] += DP[i, S - a, 0] + DP[i, S - a, 1]
        DP[i + 1, S, 2] %= MOD

    print (DP[N, S, 2])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

    for i in range(N):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    # for i in range(N + 1):
    #     print (DP[i])

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

lcs_str = ""
i, j = len(s)-1, len(t)-1
while i >= 0 and j >= 0:
	if s[i] == t[j]:
		lcs_str += s[i]
		i -= 1
		j -= 1
	else:
		if dp[i][j] > dp[i+1][j-1]:
			i -= 1
		else:
			j -= 1
print(lcs_str[::-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i, j = len(s), len(t)
while dp[i][j]:
	if s[i-1] == t[j-1]:
		ans += s[i-1]
		i -= 1
		j -= 1
	else:
		if dp[i][j] == dp[i-1][j]:
			i -= 1
		else:
			j -= 1
print(ans[::-1])
### BUGGY CODE ###

from math import ceil, sqrt
x = int(input())
# x = a**5 - b**5
# a**5 - b**5 = (a − b)(a**4 + a**3b + a**2b**2 + ab**3 + b**4)
def get_factors(n):
  set_factors = {n}
  q = n
  for i in range(1, ceil(sqrt(n))):
    if q%i == 0:
      set_factors.add(i)
      q = q//i
    if q<=1: return set_factors
  return set_factors
all_factors = get_factors(x)
def test_factor(factor):
  upper = x
  lower = 0
  while upper!=lower:
    a = (upper+lower)//2
    if a**5-(a-factor)**5 < x:
      lower = a
    elif a**5-(a-factor)**5 == x:
      return (a, a-factor)
    else:
      upper = a
  return None
for factor in all_factors:
  result = test_factor(factor)
  if result!=None:
    print(result[0], result[1])
    break

### FIXED CODE ###

def eval_pair(A, B, x):
  return A**5-B**5 == x

def get_pair(x):
  # exit early for x a power of 5.
  # apart from this, A,B don't need to be zero.
  A = int(round(x**(1/5)))
  if A**5 == x: return (A, 0)
  # try A, B:
  # +,+ and +,-
  # don't need -,- (same as +,-)
  # can't do -,+ because x is constrained positive
  # for +,+ A>=120 would give x>10**9
  # so 1<=A<120 and 1<=B<119
  valid = [(A,B) for A in range(1,120) for B in range(1,119) if eval_pair(A,B,x)]
  if valid: return valid.pop()
  # for +,- both are positive so A>=64 would give x=10**9
  # so 1<=A<64 and -64<B<-1
  valid = [(A,B) for A in range(1,64) for B in range(-1,-64, -1) if eval_pair(A,B,x)]
  if valid: return valid.pop()

x = int(input())
valid_pair = get_pair(x)
print(*valid_pair)