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

import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
count = 0
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            count += 1
            if (W + H - 2) < count:
                print("Impossible")
                exit()
            break

A[goal_y][goal_x] = "."
# pprint.pprint(A)

for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            print("Impossible")
            exit()
print("Possible")


### FIXED CODE ###

import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
count = 0
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            break
    count += 1
    if (W + H - 2) < count:
        print("Impossible")
        exit()

A[goal_y][goal_x] = "."
# pprint.pprint(A)

for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            print("Impossible")
            exit()
print("Possible")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m,l=map(int,input().split())
INF=10**10
graph=[[INF for i in range(n)] for j in range(n)]
fuel=[[INF for i in range(n)] for j in range(n)]
#for i in range(n):
#    graph[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    if c>l:continue
    graph[a][b],graph[b][a]=c,c
for i in range(n):
  for j in range(n):
    for k in range(n):
      graph[j][k]=min(graph[j][k],graph[j][i]+graph[i][k])
for i in range(n):
    for j in range(n):
        if graph[i][j]<=l:
            fuel[i][j]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      fuel[j][k]=min(fuel[j][k],fuel[j][i]+fuel[i][k])
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if fuel[s][t]==INF:print(-1)
    else:print(fuel[s][t]-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m,l=map(int,input().split())
INF=10**10
graph=[[INF for i in range(n)] for j in range(n)]
fuel=[[INF for i in range(n)] for j in range(n)]
#for i in range(n):
#    graph[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    if c>l:continue
    graph[a][b],graph[b][a]=c,c
for i in range(n):
  for j in range(n):
    for k in range(n):
      graph[j][k]=min(graph[j][k],graph[j][i]+graph[i][k])
for i in range(n):
    for j in range(n):
        if graph[i][j]<=l:
            fuel[i][j]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      fuel[j][k]=min(fuel[j][k],fuel[j][i]+fuel[i][k])
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if fuel[s][t]==INF:print(-1)
    else:print(fuel[s][t]-1)
### BUGGY CODE ###

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    A.sort()
    BC = []
    for i in range(M):
        Bi, Ci = [int(_) for _ in raw_input().split()]
        BC.append([Bi, Ci])
    BC.sort(key = lambda x: x[1], reverse = True)
    for i in range(M):
        Bi = BC[i][0]
        Ci = BC[i][1]
        cnt = 0
        while cnt < len(A) and A[cnt] < Ci:
            cnt += 1
        repl = min(cnt,Bi)
        for i in range(repl):
            A.insert(i + cnt, Ci)
        A = A[repl:]
    print sum(A)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    A.sort(reverse = True)
    BC = []
    for i in range(M):
        Bi, Ci = [int(_) for _ in raw_input().split()]
        BC.append([Bi, Ci])
    BC.sort(key = lambda x: x[1], reverse = True)
    ind_BC = 0
    ind_A = 0
    merged = []
    while ind_A < N and ind_BC < M:
        Bi = BC[ind_BC][0]
        Ci = BC[ind_BC][1]
        if A[ind_A] > Ci:
            merged.append(A[ind_A])
            ind_A += 1
        else:
            merged.extend([Ci] * Bi)
            ind_BC += 1
        if len(merged) >= N:
            break
    if len(merged) < N:
        if ind_A < N:
            merged.extend(A[ind_A:])
        elif ind_BC < M:
            for i in range(ind_BC, M):
                Bi = BC[ind_BC][0]
                Ci = BC[ind_BC][1]
                merged.extend([Bi] * Ci)
                if len(merged) >= N:
                    break
    merged = merged[:N]
    print sum(merged)

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


import numpy as np

N, K, Q = [int(x) for x in input().split()]

A = list()
while True:
    try:
        A.append(int(input()))
    except EOFError:
        break

scores = np.zeros((N), dtype=np.int32)

for a in A:
    scores[[i for i in range(N) if i != (a - 1)]] -= 1

scores = scores + K

for score in scores:
    print("Yes" if score > 0 else "No")


### FIXED CODE ###

import numpy as np

N, K, Q = [int(x) for x in input().split()]

A = list()
while True:
    try:
        A.append(int(input()))
    except EOFError:
        break

scores = np.full((N), K - Q)

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

for score in scores:
    print("Yes" if score > 0 else "No")
### BUGGY CODE ###

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

from itertools import permutations

ans = INF
for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

print(ans)


### FIXED CODE ###

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

from itertools import permutations

ans = INF
for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

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

import copy
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    X = copy.deepcopy(A)
    X.pop(i)
    X.sort()
    if N % 2 == 0:
        print(X[int(N/2)-1])
    else:
        print((X[int((N-1)/2)-1]+X[int((N-1)/2)])/2)


### FIXED CODE ###

import copy
N = int(input())
A = list(map(int, input().split()))
X = copy.deepcopy(A)
X.sort()
for i in range(N):
    if A[i] >= X[int(N/2)]:
        print(X[int(N/2)-1])
    else:
        print(X[int(N/2)])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = ''
for i in range(1,n+1):
    ans+=(str(a.index(i)+1)+' ')
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i in range(n):
    b[a[i]-1] = i+1
print(*b)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = sorted(list(set([int(x)//2 for x in input().strip().split()])), reverse=True)
lcm_d = {}
gcd_d = {}
def lcm(a, b, d, dd):
    if (a, b) in d:
        return d[(a, b)]
    ret = a * b // gcd(a, b, dd)
    ret_ = ret
    if gcd(a, b, dd) != 1:
        while (ret // a) % 2 == 0 or (ret // b) % 2 == 0:
            ret += ret_
    d[(a, b)] = ret
    return ret

def gcd(a, b, d):
    if (a, b) in d:
        return d[(a, b)]
    if b == 0:
        return a
    d[(a, b)] = gcd(b, a % b, d)
    return d[(a, b)]

lcm_ = a[0]
for aa in a[1:]:
    lcm_ = lcm(aa, lcm_, lcm_d, gcd_d)

print((m // lcm_ + 1) // 2)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = list(set([int(x)//2 for x in input().strip().split()]))

def lcm(a, b):
    return a * b // gcd(a, b)

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

def div2cnt(x):
    ret = 0
    while x % 2 == 0:
        ret += 1
        x //= 2
    return ret

cnt = div2cnt(a[0])

for i, aa in enumerate(a):
    if div2cnt(aa) != cnt:
        print(0)
        exit()
    a[i] >>= cnt
else:
    m >>= cnt

lcm_ = 1
for aa in a:
    lcm_ = lcm(lcm_, aa)
    if lcm_ > m:
        print(0)
        exit()

print((m // lcm_ + 1) // 2)
### BUGGY CODE ###

from collections import deque
from heapq import heappush, heappop

N, M = map(int, input().split())

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N
ans = [-1] * N

que = [(0, root, -1)]
while que:
    dp, now, pr = heappop(que)
    dp *= -1

    if depth[now] >= dp:
        continue
    depth[now] = dp
    ans[now] = pr + 1

    for ch in child[now]:
        if depth[ch] < dp + 1:
            heappush(que, (-(dp + 1), ch, now))

ans[root] = 0
print(*ans, sep='\n')



### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
ans = [-1] * N

# 葉からの検索を行う
@lru_cache(maxsize=None)
def search(now):
    if now == root:
        ans[now] = 0
        return 0
    ret = -1
    for pr in parent[now]:
        depth = search(pr)
        if depth > ret:
            ans[now] = pr + 1
            ret = depth
    return ret + 1

for i in range(N):
    search(i)

print(*ans, sep='\n')
### BUGGY CODE ###

from scipy.sparse.csgraph import shortest_path
import numpy as np
import sys

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

N, M = map(int, input().split())
A = []
B = []
neighbor = np.array([[0 for x in range(N)] for y in range(N)])
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    neighbor[a][b] = 1
    neighbor[b][a] = 1

ans = []
for i in range(1,N):
    d, p = shortest_path(neighbor, return_predecessors=True, indices=[0, i])
    next_sign = get_path(0,i,p)
    if next_sign:
        ans.append(next_sign[-2]+1)
    else:
        print("No")
        sys.exit(0)

print("Yes")
for i in range(N-1):
    print(ans[i])


### FIXED CODE ###

from collections import deque

N,M = map(int, input().split())
ways = [[] for _ in range(N+1)]

for i in range(M):
    a,b = map(lambda x: int(x), input().split())
    ways[a].append(b)
    ways[b].append(a)

dq = deque([1])
sign = [None] * (N+1)
sign[0] = 0
sign[1] = 0

while(dq):
    now = dq.popleft()
    for w in ways[now]:
        if not sign[w]:
            sign[w] = now
            dq.append(w)

if None in sign:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(sign[i])
### BUGGY CODE ###

from functools import lru_cache

s = input()
s_len = len(s)
n = 2019
n_len = len(str(n))
result = 0
a = 202


@lru_cache(maxsize=128)
def reduce_number(s):
    left = int(s[:-1])
    right = a * int(s[-1])
    result = str(left + right)
    return result


@lru_cache(maxsize=128)
def is_multiple(s):
    _s = s
    while True:
        _s = reduce_number(_s)
        _s_int = int(_s)
        if _s_int == n:
            return True
        elif _s_int < n:
            return False


for i in range(s_len - n_len):
    for j in range(i + n_len, s_len + 1):
        m = s[i:j]
        if is_multiple(m):
            result += 1
            break
print(result)

### FIXED CODE ###

s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

p = 1
d = 0
for t in reversed(s):
    d += int(t) * p
    m = d % n
    mod_list[m] += 1
    p *= 10
    p %= 2019

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)
### BUGGY CODE ###

cou = int(input())
bars = input().split()
two = [0, 0]
i = 0
ca = len(bars)
while i < ca:
    if bars[i] in two:
        pass
    else:
        if bars.count(bars[i]) > 3:
            two.extend(bars[i])
            two.extend(bars[i])
        elif bars.count(bars[i]) > 1:
            two.extend(bars[i])
        else:
            pass
    i += 1
two.sort(key=int)
print(int(two[-1]) * int(two[-2]))


### FIXED CODE ###

n=input()
a = list(map(int, input().split()))
a.sort()
h, w =0, 0
while True:
    try:
        if a[-1] == a[-2]:
            h = a[-1]
            a.pop()
            a.pop()
            break
        else:
            a.pop()
    except:
        break

while True:
    try:
        if a[-1] == a[-2]:
            w = a[-1]
            a.pop()
            a.pop()
            break
        else:
            a.pop()
    except:
        break
print(h*w)
### BUGGY CODE ###

import numpy as np
from fractions import gcd

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

p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
 
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b
def lcm(a,b):
    g=gcd(a,b)
    #return ((a*b)*pow(g,p-2,p))%p
    return a//gcd(a,b)*b

LCM=1
for x in A:
    LCM=lcm(LCM,x)



#print(LCM)
ans=0
LCM%=p
for i in range(N):
    #ans+=(LCM*inv[A[i]])%p
    ans+=(LCM*pow(A[i],p-2,p))%p
    ans%=p
print(ans)

### FIXED CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

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

n=int(input())
p=list(map(int,input().split()))
sum=0
for i in range(n):
  count=0
  l=i
  for j in range(l):
    if p[l]<=p[j]:
      count+=1
  if count==i:
    sum+=1
print(str(sum))


### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
count=0
min=1000000
for i in range(n):
  if p[i]<=min:
    count+=1
    min=p[i]
  
print(str(count))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
from itertools import combinations

N,M = map(int,input().split())
alist = []
for cmb in combinations([i for i in range(1,M)],N-1):
  cmb = [0] + list(cmb) + [M]
  tmp_a = sorted([cmb[i]-cmb[i-1] for i in range(1,N+1)])
  if tmp_a not in alist: alist.append(tmp_a)

ans = -float('inf')
for a in alist:
  ans = max(ans, reduce(gcd,a))
print(ans)

### FIXED CODE ###

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

ans = -float('inf')
N,M = map(int,input().split())
for div in make_divisors(M):
  if M//div >= N: ans = max(ans, div)
print(ans)
### BUGGY CODE ###

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

acnt = 0
bcnt = 0
while True:
    acnt += a
    if acnt + bcnt >= n:
        acnt -= (acnt + bcnt) - n
        break
    bcnt += b
    if acnt + bcnt >= n:
        break
print(acnt)


### FIXED CODE ###

n, a, b = map(int, input().split())
amari = n % (a+b)
sho = n // (a+b)
if n <= a:
    print(n)
elif amari == 0:
    print(a*sho)
elif amari < a:
    print(a*sho + amari)
else:
    print(a*sho + a)
### BUGGY CODE ###

N = int(input())
S = input()

r = 0
g = 0
b = 0
ans = 0
for s in S:
    if s == "R":
        r += 1
    elif s == "G":
        g += 1
    else:
        b += 1

for i in range(len(S) - 2):
    j = 1
    if S[i] == "R":
        ans += g * b
        r -= 1
    elif S[i] == "G":
        ans += r * b
        g -= 1
    else:
        ans += r * g
        b -= 1
    
    while not(i + j +j >= len(S)):
        if S[i] == "R":
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
        j += 1
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
tmp = Counter(S)
# print(tmp)
r = tmp["R"]
g = tmp["G"]
b = tmp["B"]
ans = 0
# for s in S:
#     if s == "R":
#         r += 1
#     elif s == "G":
#         g += 1
#     else:
#         b += 1

for i in range(len(S) - 2):
    j = 1
    if S[i] == "R":
        ans += g * b
        r -= 1
    elif S[i] == "G":
        ans += r * b
        g -= 1
    else:
        ans += r * g
        b -= 1
    
    while not (i + j + j >= len(S)):
        if S[i] == "R":
            if S[i + j] == "R":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "G":
                j += 1
                continue
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "B":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
        j += 1
print(ans)
### BUGGY CODE ###

import numpy as np
H,W = map(int,input().split())

field = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    field[i] = str(input());

L = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if field[i][j] == ".":
            ii = i
            jj = j
            while (ii < H and field[ii][jj] == "."):
                L[i][j] += 1
                ii += 1
            ii = i
            jj = j
            while (ii >= 0 and field[ii][jj] == "."):
                L[i][j] += 1
                ii -= 1
            ii = i
            jj = j
            while (jj < W and field[ii][jj] == "."):
                L[i][j] += 1
                jj += 1
            ii = i
            jj = j
            while (jj >= 0 and field[ii][jj] == "."):
                L[i][j] += 1
                jj -= 1

L = np.array(L)
ans = L
ans = L.max()
#ans = L[idx]
#ans = max(ans)
#ans = ans-3

print(ans-3)







### FIXED CODE ###

def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    H, W = LI()
    S = [SI() for _ in range(H)]
    width = [[0]*W for _ in range(H)]
    height = [[0]*W for _ in range(H)]
    for i in range(H):
        cur = 0; keep = []
        for j in range(W):
            if S[i][j]==".":
                cur +=1
                keep.append(j)
            else:
                for k in keep:
                    width[i][k] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                width[i][k] = cur
    for j in range(W):
        cur = 0; keep = []
        for i in range(H):
            if S[i][j]==".":
                cur +=1
                keep.append(i)
            else:
                for k in keep:
                    height[k][j] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                height[k][j] = cur
    ans = 0
    for i in range(H):
        for j in range(W):
            cur = width[i][j] + height[i][j]
            if ans<cur:
                ans = cur
    print(ans-1)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n - 1):
        tmp_sum = sum(a[:i+1])
        ans += tmp_sum * a[i+1]
    m = 10 ** 9 + 7
    print(ans % m)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

X = ri()

def get_divisors(X):
	if X == 1:
		return [1]
	i = 2
	div = []
	while i*i <= X:
		if X % i == 0:
			X //= i
			div.append(i)
		else:
			i += 1
	if X > 1:
		div.append(X)
	return div

#for i in range(1, 10):
#	print(i, get_divisors(i))

def f(x, y):
	# x**4+y**4+x**2*y**2 + x**3*y+x*y**3
	return (y**4+x*y**3+x**2*y**2+x**3*y+x**4) * (x-y)

def search(d):
	y = 0
	while True:
		x = y+d
		v = f(x, y)
		#print(v)
		#print(x, y, v)
		if v == X:
			print(x, y)
			exit()
		if v > X:
			break
		y += 1
	y = -1
	while True:
		x = y+d
		if x <= 0:
			break
		v = f(x, y)
		#print(x, y, v)
		if v == X:
			print(x, y)
			exit()
		if v <= 0:
			break
		y -= 1

import itertools
def comb(divs):
	for i in range(1, len(divs)+1):
		for c in itertools.combinations(divs, i):
			m = 1
			for n in c:
				m *= n
			yield m

divs = get_divisors(X)
#print(divs)
visited = {}
for d in comb(divs):
#for d in set(divs):
	if d in visited: continue
	search(d)
	visited[d] = 1



### FIXED CODE ###

import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

X = ri()

for a in range(-200, 200):
	for b in range(-200, a):
		if a**5 - b**5 == X:
			print(a, b)
			exit()