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

x=int(input())
a=0
b=0
while a**5 < x:
    a+=1
a-=1
while a**5 - b**5 != x and a**5 + b**5 != x:
    b+=1
if a**5 - b**5 == x:
    print(a,b)
else:
    print(a,b*-1)

### FIXED CODE ###

x = int(input())
for a in range(1001):
    for b in range(1001):
        if (a**5)-(b**5)==x:
            print(a,b)
            exit()
        if (a**5)+(b**5)==x:
            print(a,-1*b)
            exit()
        if (b**5)-(a**5)==x:
            print(-1*a,-1*b)
            exit()
### BUGGY CODE ###

import copy
N = int(input())
A = [[int(Aij) for Aij in input().split()] for _ in range(N)]

n = len(A)
d = 0
for i in range(n):
    for j in range(i + 1, n):
        flag = True
        for k in range(n):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] < A[i][j]:
                print('-1')
                exit()
            elif A[i][k] + A[k][j] == A[i][j]:
                flag = False
                break
        if flag:
            d += A[i][j]
print(d)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

A2 = floyd_warshall(A, directed=False)

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,w,k = nm()
s = [list(map(int, list(ns()))) for _ in range(h)]
ans = h*w
for bit in range(1<<(h-1)):
    d = dict()
    l = list()
    q = [0]
    for j in range(h-1):
        if bit & (1<<j):
            l.append(tuple(q))
            q = list()
        q.append(j+1)
    l.append(tuple(q))
    t = len(l)
    for i in range(t):
        for x in l[i]:
            d[x] = i
    cur = bin(bit).count('1')
    g = [0]*t
    for j in range(w):
        c = [0]*t
        for i in range(h):
            c[d[i]] += s[i][j]
        if max(c) > k:
            cur = h*w
            break
        for i in range(t):
            g[i] += c[i]
        if max(g) > k:
            cur += 1
            g = c[:]
    if ans > cur: ans = cur
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,w,k = nm()
s = [list(map(int, list(ns()))) for _ in range(h)]
ans = h*w
for bit in range(1<<(h-1)):
    d = dict()
    l = list()
    q = [0]
    for j in range(h-1):
        if bit & (1<<j):
            l.append(tuple(q))
            q = list()
        q.append(j+1)
    l.append(tuple(q))
    t = len(l)
    for i in range(t):
        for x in l[i]:
            d[x] = i
    cur = bin(bit).count('1')
    g = [0]*t
    for j in range(w):
        c = [0]*t
        for i in range(h):
            c[d[i]] += s[i][j]
        if max(c) > k:
            cur = h*w
            break
        for i in range(t):
            g[i] += c[i]
        if max(g) > k:
            cur += 1
            g = c[:]
    if ans > cur: ans = cur
print(ans)
### BUGGY CODE ###

from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = min(warp[ny][nx],warp[y][x]+1)
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])

### FIXED CODE ###

from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "#"
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])
### BUGGY CODE ###

s=raw_input()
t=raw_input()

len_s=len(s)
len_t=len(t)

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=[ [ "" for j in range(len_t+1) ] for i in range(len_s+1)   ]

for i in range(1,len_s+1):
	for j in range(1,len_t+1):
		if s[i]==t[j]:
			dp[i][j]=dp[i-1][j-1]+1
			S[i][j]=S[i-1][j-1]+s[i]
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )
			if dp[i-1][j]>=dp[i][j-1]:
				S[i][j]=S[i-1][j]
			else:
				S[i][j]=S[i][j-1]


print S[-1][-1]


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
s=raw_input()
t=raw_input()

len_s=len(s)
len_t=len(t)

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=""
l=0

for i in range(1,len_s+1):
	for j in range(1,len_t+1):
		if s[i]==t[j]:
			dp[i][j]=dp[i-1][j-1]+1
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )


ans=""
def lcs(i,j):
	global ans
	if dp[i][j]==0:
		return
	else:
		if s[i]==t[j]:
			lcs(i-1,j-1)
			ans+=s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				lcs( i-1, j )
			else:
				lcs( i, j-1)

lcs(len_s, len_t)
print ans
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(H: int, W: int, S: "List[str]"):
    S = np.array(S)
    sh = np.zeros((H, W),dtype=np.int)
    sw = np.zeros((W, H),dtype=np.int)

    for i, a in enumerate(S):
        left = np.arange(1, len(a)+1)
        left[a==0] = 0
        left = np.maximum.accumulate(left)
        a_ = a[::-1]
        right = np.arange(1,len(a)+1)
        right[a_==0] = 0
        right = np.maximum.accumulate(right)
        right = len(a)+1 - right[::-1]
        k = ((right-left) - 1)
        k[a==1] =0
        sh[i] = k

    for i, a in enumerate(S.T):
        left = np.arange(1, len(a)+1)
        left[a==0] = 0
        left = np.maximum.accumulate(left)
        a_ = a[::-1]
        right = np.arange(1,len(a)+1)
        right[a_==0] = 0
        right = np.maximum.accumulate(right)
        right = len(a)+1 - right[::-1]
        k = ((right-left) - 1)
        k[a==1] =0
        sw[i] = k

    print(np.max(sw+sh.T)-1)



    # for w in range(W):
        # for h in range(H):

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [[ int(_.replace(".", "0").replace("#", "1")) for _ in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def solve(H: int, W: int, S: "List[int]"):
    # print(S)

    hcnts = [[0]*W for _ in range(H)]
    for h in range(H):
        hcnts[h][0] = S[h][0]
        for t in range(1,W):
            hcnts[h][t] = (S[h][t]+hcnts[h][t-1])*S[h][t]
    for h in range(H):
        for t in range(W-2,-1,-1):
            hcnts[h][t] = max(hcnts[h][t],hcnts[h][t+1])*bool(hcnts[h][t])

    wcnts = [[0]*W for _ in range(H)]
    for h in range(W):
        wcnts[0][h] = S[0][h]
        for t in range(1,H):
            wcnts[t][h] = (S[t][h]+wcnts[t-1][h])*S[t][h]
    for h in range(W):
        for t in range(H-2,-1,-1):
            wcnts[t][h] = max(wcnts[t][h],wcnts[t+1][h])*bool(wcnts[t][h])
    # print(hcnts)
    # print(wcnts)
    a = [hcnts[h][w]+wcnts[h][w]-1 for h in range(H) for w in range(W)]
    print(max(a))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [[ int(_.replace(".", "1").replace("#", "0")) for _ in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()
### 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()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
B = [BC[k][0] for k in range(M)]
C = [BC[k][1] for k in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A = A + [BC[i][1]] * BC[i][0]
    A.sort(reverse=True)
    if len(A) >= 2 * N:
        break

print(sum(A[:N]))


### FIXED 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()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A.extend([BC[i][1]] * BC[i][0])
    if len(A) >= 2 * N:
        break

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

# coding: utf-8
import sys
import math
import decimal

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

decimal.getcontext().prec = 12
N, K = lr()
answer = decimal.Decimal(0)
for x in range(1, N+1):
    power = 0
    while x < K:
        x *= 2
        power += 1
    answer += decimal.Decimal(.5) ** power

answer /= N
print('{:.12f}'.format(answer))


### FIXED CODE ###

N,K = map(int,input().split())
#サイコロが出た面を１から計算
ans = 0
for i in range(1,N+1):
    num = 0
    # iに２の何乗を掛けるとKを超えるか
    j = 0
    while True:
        if i * 2 ** j >= K:
            num = j
            break
        j += 1
    ans += (1/N) * (1/2) ** num
print(ans)
### BUGGY CODE ###

def f():
    h, w, n = map(int, input().split())
    md = 10 ** 9 + 7
    k = [list(map(int, input().split())) for _ in range(n)] + [[h, w]]

    # 壁をマンハッタン距離順に
    k.sort(key=lambda x: x[0] + x[1])

    # 階乗と逆元とコンビネーションを事前準備
    fct = [1] * (h + w + 1)
    re_fct = [1] * (h + w + 1)
    fct_i = 1
    for i in range(1, h + w + 1):
        fct_i = fct_i * i % md
        fct[i] = fct_i
    # fct_i**(md-2)が逆元re_i
    re_i = 1
    p = md - 2
    while p:
        if p & 1:
            re_i = re_i * fct_i % md
        p >>= 1
        fct_i = fct_i ** 2 % md
    for i in range(h + w, 1, -1):
        re_fct[i] = re_i
        re_i = re_i * i % md
    cmb = lambda a, b: fct[a] * re_fct[b] * re_fct[a - b] % md

    # こっから本体
    dp = [0] * (n + 1)
    for i, [r, c] in enumerate(k):
        dpi = cmb(r + c - 2, r - 1) % md
        for j in range(i):
            dr, dc = r - k[j][0], c - k[j][1]
            if dr >= 0 and dc >= 0:
                dpi = (dpi - dp[j] * cmb(dr + dc, dr)) % md
        dp[i] = dpi
    print(dp[-1])


f()


### FIXED CODE ###

def f():
    h, w, n = map(int, input().split())
    md = 10 ** 9 + 7
    k = [list(map(int, input().split())) for _ in range(n)] + [[h, w]]

    # 壁をマンハッタン距離順に
    k.sort(key=lambda x: x[0] + x[1])

    # 階乗と逆元とコンビネーションを事前準備
    fct = [1]
    re_fct = []
    fct_i = 1
    for i in range(1, h + w + 1):
        fct_i = fct_i * i % md
        fct += [fct_i]
    # fct_i**(md-2)が逆元re_i
    re_i = 1
    p = md - 2
    while p:
        if p & 1:
            re_i = re_i * fct_i % md
        p >>= 1
        fct_i = fct_i ** 2 % md
    for i in range(h + w, -1, -1):
        re_fct += [re_i]
        re_i = re_i * i % md
    re_fct = re_fct[::-1]
    cmb = lambda a, b: fct[a] * re_fct[b] * re_fct[a - b] % md

    # こっから本体
    dp = [0] * (n + 1)
    for i, [r, c] in enumerate(k):
        dpi = cmb(r + c - 2, r - 1) % md
        for j in range(i):
            dr, dc = r - k[j][0], c - k[j][1]
            if dr >= 0 and dc >= 0:
                dpi = (dpi - dp[j] * cmb(dr + dc, dr)) % md
        dp[i] = dpi
    print(dp[-1])


f()
### BUGGY CODE ###

import collections
import math
def C(n, r):
    if n-r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = {}
sm = 0
for k,v in c.most_common():
    d.update({k:v})
    sm += C(v,2)

for a in A:
    print (sm - C(d.get(a),2) + C(d.get(a)-1,2) )


### FIXED CODE ###

import collections
import math

def C(n):
    if n-2 < 0:
        return 0
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
#d = {}
d = [-1]*200010
Cf = [C(i) for i in range(200010)]
sm = 0
for k,v in c.most_common():

    d[k] = v
    sm += C(v)

for a in A:
    print (sm - Cf[d[a]] + Cf[d[a]-1])
### BUGGY CODE ###

def astar(start, goal, S, H, W):
  if S[start[0]][start[1]] == '#' or S[goal[0]][goal[1]] == '#':
    return -1
  else:
    INF = 10**9
    D = [[INF]*W for h in range(H)]
    D[start[0]][start[1]] = 0
    next_node = [start]
    while next_node:
      now_y, now_x = next_node.pop()
      d = D[now_y][now_x]
      for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if now_y+y<0 or now_y+y>=H or now_x+x<0 or now_x+x>=W:
          continue
        if S[now_y+y][now_x+x] == '.':
          if D[now_y+y][now_x+x] > d + 1:
            D[now_y+y][now_x+x] = D[now_y][now_x] + 1
            next_node.append([now_y+y, now_x+x])
    
    if D[goal[0]][goal[1]] < INF:
      return D[goal[0]][goal[1]]
    else:
      return -1


H, W = map(int, input().split())
nodes = []
for h in range(H):
  for w in range(W):
    nodes.append([h, w])

S = []
for h in range(H):
  S.append(list(input()))

ans = 0
num_nodes = len(nodes)
for i in range(num_nodes):
  for j in range(i+1, num_nodes):
    ans = max(ans, astar(nodes[i], nodes[j], S, H, W))

print(ans)

### FIXED CODE ###

from collections import deque

def astar(start, S, H, W):
  if S[start[0]][start[1]] == '#':
    return -1
  else:
    INF = 10**9
    D = [[INF]*W for h in range(H)]
    D[start[0]][start[1]] = 0
    next_node = deque([start])
    max_d = 0
    while next_node:
      now_y, now_x = next_node.popleft()
      d = D[now_y][now_x]
      for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if now_y+y<0 or now_y+y>=H or now_x+x<0 or now_x+x>=W:
          continue
        if S[now_y+y][now_x+x] == '.':
          if D[now_y+y][now_x+x] > d + 1:
            D[now_y+y][now_x+x] = D[now_y][now_x] + 1
            max_d = max(max_d, D[now_y+y][now_x+x])
            next_node.append([now_y+y, now_x+x])
    
    return max_d

H, W = map(int, input().split())
nodes = []
for h in range(H):
  for w in range(W):
    nodes.append([h, w])

S = []
for h in range(H):
  S.append(list(input()))

ans = 0
for start in nodes:
  ans = max(ans, astar(start, S, H, W))

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

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

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

import sys
import numpy as np
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res+=N
    res*=1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=np.full((310,310,310),-1,dtype='float')
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res=(res+N)*1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()
### BUGGY CODE ###

N = int(input())
A = 1
B = 1
for _ in range(N):
    a, b = map(int, input().split())
    if a == b:
        A = max(A, B)
        B = max(A, B)
    elif a < b:
        if A%a == 0:
            pass
        else:
            A = (A//a+1)*a
        while (A//a)*b < B:
            A += a
        B = (A//a)*b
    else:
        if B%b == 0:
            pass
        else:
            B = (B//b+1)*b
        while (B//b)*a < A:
            B += b
        A = (B//b)*a
print(A+B)

    

### FIXED CODE ###

N = int(input())
A = 1
B = 1
for _ in range(N):
    a, b = map(int, input().split())
    if a == b:
        A = max(A, B)
        B = max(A, B)
    else:
        if A%a == 0:
            aa = A//a
        else:
            aa = A//a + 1
        if B%b == 0:
            bb = B//b
        else:
            bb = B//b + 1
        tmp = max(aa, bb)
        A = tmp*a
        B = tmp*b

print(A+B)
### BUGGY CODE ###

def nCr(n,r,mod = 10**9+7):
    r = min(n-r,r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) %mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) %mod


n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

A.sort()

mini_count = 0
maxim_count = 0

for i in range(n-k+1):
    mini = A[i]
    pattern = nCr(n-i-1, k-1)
    mini_count += mini * pattern % mod
    mini_count %= mod


for i in range(1, n-k+2):
    maxim = A[-i]
    pattern = nCr(n-i, k-1)
    maxim_count += maxim * pattern % mod
    maxim_count %= mod

ans = maxim_count - mini_count
ans %= mod

print(ans)

### FIXED CODE ###

P = 10**9 + 7
N = 1000000
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]



n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

A.sort()

mini_count = 0
maxim_count = 0
pattern = 1
for i in range(n-k, -1, -1):
    mini = A[i]
    mini_count += mini * pattern % mod
    mini_count %= mod
    pattern = pattern * (n-i) * inv_t[n-i-k+1] % mod


pattern = 1
for i in range(n-k+1, 0, -1):
    maxim = A[-i]
    maxim_count += maxim * pattern % mod
    maxim_count %= mod
    pattern = pattern * (n-i+1) * inv_t[n-i-k+2] % mod

ans = maxim_count - mini_count
ans %= mod

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

a = []
x = 1

n = int(input())
a = input().split()

for i in range(n):
    a[i] = int(a[i])
    x = x * a[i]
    
if x <= 10**18:
    print(x)
elif x > 10**18:
    print(-1)

### FIXED CODE ###

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

for i in range(n):
  ans = ans * a[i]
  if ans > 10**18:
    ans = -1
    break

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

def main():
    s = input()
    q = int(input())
    jun = True
    for _ in range(q):
        qu = input()
        if qu == '1':
            jun = not jun
        else:
            if qu[2] == '1':
                if jun:
                    s = qu[4] + s
                else:
                    s = s + qu[4]
            else:
                if jun:
                    s = s + qu[4]
                else:
                    s = qu[4] + s
    if not jun:
        s = s[::-1]
    print(s)
main()

### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    jun = True
    mae = ""
    ushiro = ""
    for _ in range(q):
        qu = input()
        if qu == '1':
            jun = not jun
        else:
            if qu[2] == '1':
                if jun:
                    mae = qu[4] + mae
                else:
                    ushiro = ushiro + qu[4]
            else:
                if jun:
                    ushiro = ushiro + qu[4]
                else:
                    mae = qu[4] + mae
    s = mae + s + ushiro
    if not jun:
        s = s[::-1]
    print(s)
main()
### BUGGY CODE ###

import itertools

N = int(input())
O = range(1, N+1)
MODS = range(1, N+1)
ans = 0

for i in range(N):
    M = O[i] % MODS[(i+1) % N]
    ans += M

print(ans)


### FIXED CODE ###

N = int(input())

print((N * (N - 1)) // 2)