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

from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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



g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    sys.exit()

A=[i for i in A if i != 1]    

B=[pf(A[i]) for i in range(len(A))]
B=sum(B,[])

if len(B) == len(set(B)):
    print("pairwise coprime")
    
else:
    print("setwise coprime")
    

### FIXED CODE ###

from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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



g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    sys.exit()

deta = set()
for a in A:
    a=pf(a)
    
    for p in a:
        if p in deta:
            print("setwise coprime")
            sys.exit()
            
        deta.add(p)


print("pairwise coprime")
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        y, x = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                Q.append((ny,nx))

    ans = 0
    for h in range(H):
        ans = max(ans, max(visited[h]))

    print(ans)




if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    visited = [[float('inf')] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
                visited[h][w] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == float('inf'):
                    visited[ny][nx] = now + 1
                    Q.append((ny,nx))
                    ans = max(ans, now + 1)

    print(ans)




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

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0)
    s = input().strip()
    ls, rs = s, s
    l, r = 0, N
    while s != 'Vacant':
        m = (l + r) // 2
        print(m)
        s = input().strip()
        if (m - l) % 2 == 0 and s != ls:
            r = m
        elif (m - l) % 2 == 1 and s == ls:
            r = m
        elif (r - m) % 2 == 0 and s != rs:
            l = m
        elif (r - m) % 2 == 1 and s == rs:
            l = m

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0, flush=True)
    s = input().strip()
    if s == 'Vacant':
        return True
    ls, rs = s, s
    l, r = 0, N
    while True:
        m = (l + r) // 2
        print(m, flush=True)
        s = input().strip()
        if s == 'Vacant':
            return True
        if (m - l) % 2 == 0 and s != ls:
            r = m
            rs = s
        elif (m - l) % 2 == 1 and s == ls:
            r = m
            rs = s
        elif (r - m) % 2 == 0 and s != rs:
            l = m
            ls = s
        elif (r - m) % 2 == 1 and s == rs:
            l = m
            ls = s

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

# coding: utf-8
# Your code here!
import fractions

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

def yaku(num):
    temp=[]
    for i in range(2,-int(-num**0.5//1)+1):
        if num%i==0:
            temp.append(i)
            temp.append(num//i)
    temp=list(set(temp))
    temp.append(num)
    temp.sort()
    return temp

koyaku=fractions.gcd(A,B)

cand=yaku(min(A,B))
#print(cand)

count=0

for i in cand:
    judge=True
    while koyaku%i==0:
        koyaku//=i
        if judge==True:
            count+=1
            judge=False
    if koyaku==1:
        break
print(count+1)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import fractions

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

def yaku(num):
    temp=[]
    for i in range(2,-int(-num**0.5//1)+1):
        if num%i==0:
            temp.append(i)
            temp.append(num//i)
    temp=list(set(temp))
    if num!=2:
        temp.append(num)
    temp.sort()
    return temp

koyaku=fractions.gcd(A,B)

cand=yaku(min(A,B))
#print(cand)

if cand[0]==1:
    print(1)
    exit()

count=0

for i in cand:
    judge=True
    while koyaku%i==0:
        koyaku//=i
        if judge==True:
            count+=1
            judge=False
    if koyaku==1:
        break
print(count+1)
### BUGGY CODE ###

from collections import deque as dq
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = min(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = min(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])



### FIXED CODE ###

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 2 << 31
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = [[0] * M for _ in range(2 ** 12)]
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if vis[i][j] == 1:
    continue
  vis[i][j] = 1
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])
### BUGGY CODE ###

n = int(input())

a = list(int(i) for i in input().split())
b = []
for i in range(0,len(a)):
    b.append(a[i])


def solve(cnt,A,N):
    for i in range(1, N):
        if sum(A[0:i])>0:
            while sum(A[0:i+1])>=0:
                A[i]-=1
                cnt+=1
        else:
            while sum(A[0:i+1])<=0:
                A[i]+=1
                cnt+=1
    return cnt

cnt1=0
if b[0]<=0:
    while b[0]<=0:
        b[0]+=1
        cnt1+=1

ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    while a[0]>=0:
        a[0]-=1
        cnt2+=1

ans2=solve(cnt2,a,n)
print(min(ans1,ans2))


### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))
### BUGGY CODE ###

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]
items.insert(0, (0, 0))

v_max = sum([x[1] for x in items])

dp = [[10**13 for _ in range(v_max+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(v_max+1):
        # print(i,j)
        # take item
        if j-items[i][1] >= 0:
            dp[i][j] = dp[i-1][j-items[i][1]]+items[i][0]

        dp[i][j] = min(dp[i][j], dp[i-1][j])

# print(dp[N])

ans = 0
for i in range(v_max+1):
    if dp[N][i] <= W:
        ans = i

print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
items = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        items[0].append(v)
    else:
        items[w-w0].append(v)

items = [[0]+sorted(items[i], reverse=True) for i in range(4)]
for i in range(4):
    for j in range(1, len(items[i])):
        items[i][j] += items[i][j-1]

ans = 0
for i in range(len(items[0])):
    for j in range(len(items[1])):
        for k in range(len(items[2])):
            for l in range(len(items[3])):
                if w0*(sum((i, j, k, l))) + j + k*2+l*3 <= W:
                    ans = max(
                        ans, sum((items[0][i], items[1][j], items[2][k], items[3][l])))

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

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

for i in range(N - 1):
    for j in range(i + 1, N):
        sum += A[i] * A[j]


sum = sum % (10 ** 9 + 7)

print(sum)


### FIXED CODE ###

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

num_sum = 0
temp_sum_num = sum(A)

for i in range(N - 1):
    temp_sum_num -= A[i]
    num_sum += A[i] * temp_sum_num


num_sum = num_sum % (10 ** 9 + 7)

print(num_sum)
### BUGGY CODE ###

# D - Banned K(高速版)
N = int(input())
A = list(map(int, input().split()))

import copy as c
C = []

for i in range(N):
    C.append(A.count(i+1))

C_tmp = [s for s in C if s > 1]

sum0 = 0
for j in C_tmp:
    sum0 = sum0 + j*(j-1)/2

for a in A:
    if C[a-1] >= 2:
        d = C[a-1] - 1
    else:
        d =0
    sum = int(sum0 - d)
    print(sum)

### FIXED CODE ###

import collections


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

    counter = collections.Counter(A)
    ans = 0

    for i in counter.values():
        ans += i * (i - 1) // 2

    for a in A:
        count = counter[a]
        print(ans - (count * (count - 1) // 2) +
              ((count - 1) * (count - 2) // 2))


resolve()
### BUGGY CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import copy
N=int(input())
A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1

playerlst=set([i for i in range(N)])

count=0
nlst=copy.copy(playerlst)
while playerlst:
    flag=0
    lst=copy.copy(playerlst)
    playedlst=set()
    while nlst:
        p=nlst.pop()
        if p in lst:
            p2=A[p][-1]
            if p2 in lst and A[p2][-1]==p:
                flag=1
                A[p].pop()
                A[p2].pop()
                lst.remove(p)
                lst.remove(p2)
                if p2 in nlst:
                    nlst.remove(p2)
                playedlst.add(p)
                playedlst.add(p2)
                if not A[p]:
                    playerlst.remove(p)
                if not A[p2]:
                    playerlst.remove(p2)
    if not flag:
        print(-1)
        exit()
    count+=1
    nlst=copy.copy(playedlst)
print(count)


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import copy
N=int(input())
A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1

playerlst=set([i for i in range(N)])

count=0
nlst=copy.copy(playerlst)
while playerlst:
    flag=0
    lst=set()
    playedlst=set()
    while nlst:
        p=nlst.pop()
        if not p in lst and p in playerlst:
            p2=A[p][-1]
            if not p2 in lst and p2 in playerlst:
                if A[p2][-1]==p:
                    flag=1
                    A[p].pop()
                    A[p2].pop()
                    lst.add(p)
                    lst.add(p2)
                    if p2 in nlst:
                        nlst.remove(p2)
                    playedlst.add(p)
                    playedlst.add(p2)
                    if not A[p]:
                        playerlst.remove(p)
                    if not A[p2]:
                        playerlst.remove(p2)
    if not flag:
        print(-1)
        exit()
    count+=1
    nlst=copy.copy(playedlst)
print(count)
### BUGGY CODE ###

import sys

primes = [2]
for line in sys.stdin:
  try:
    n = int(line)
    if n > max(primes):
      for i in range(max(primes) + 1, n + 1):
        if i % 2 == 0 or i % 3 == 0:
          continue
        primes.append(i)
        for p in primes:
          if i % p == 0 and i != p:
            primes.pop()
            break
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break

### FIXED CODE ###

import sys
import math

# Sieve of Eratosthenes
N = 999999
searchList = list(range(3, N + 1, 2))
primes = [2]
while True:
  top = searchList.pop(0)
  primes.append(top)
  if top > math.sqrt(N):
    break
  searchList = [s for s in searchList if s % top != 0]
primes.extend(searchList)

# solve
for line in sys.stdin:
  try:
    n = int(line)
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break
### BUGGY CODE ###

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

mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now= now*A[-i-1]%mod
        # now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        l+=2
    else:
        ans*= pl%mod
        r-=2
print(ans%mod)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
mod=10**9+7
ans=1

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

l=0
r=N-1
if K%2==1:
    ans=ans*A[r]
    r-=1

for _ in range(K//2):
    ml=A[l]*A[l+1]
    mr=A[r]*A[r-1]
    if ml>mr:
        ans=ans*ml%mod
        l+=2
    else:
        ans=ans*mr%mod
        r-=2

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

N = int(input())

s_list = {}
cnt = 0
for i in range(N):
    candidate = input()

    # Check key
    if (candidate[0] in s_list) == False:
        tmp = {candidate[0]:[]}
        s_list.update(tmp)

    for s in s_list[candidate[0]]:
        if candidate == s:
            break
    else:
        cnt += 1
        s_list[candidate[0]].append(candidate)

print(cnt) 

### FIXED CODE ###

s_list = []
N = int(input())
for _ in range(N):
    s_list.append(input())

print(len(set(s_list)))
### BUGGY CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
L = [X[i+1] - X[i] for i in range(len(X)-1)]
k = 0
while k < N-1 and L != []:
    L.remove(max(L))
    k += 1
print(sum(L) if X != [] else 0)

### FIXED CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
L = [X[i+1] - X[i] for i in range(len(X)-1)]
L.sort(reverse=True)
K = L[N-1:]
print(sum(K) if K != [] else 0)
### BUGGY CODE ###

N=int(input())
S=input()
left_count=0
right_count=0
ans=N
for i in range(N):
    right_count=S[i+1:].count('E')
    ans=min(ans, right_count+left_count)
    if S[i]=='W':
        left_count+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
L=[]
w=0
e_count=0
ans=N

for i in range(N):
    L.append(w)
    if S[i]=='W':
        w+=1

for i in range(N):
    ans=min(L[N-i-1]+e_count,ans)
    if S[N-i-1]=='E':
            e_count+=1

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

import sys
input = sys.stdin.readline
import math
import numpy as np

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

a = np.array(a)
tmp = (a/2).astype(np.int)

import fractions
lcm = tmp[0]
for i in range(1, n):
    lcm = lcm * tmp[i] // fractions.gcd(lcm, tmp[i])


def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(0, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

a = [ai >> 1 for ai in a]

import fractions
from functools import reduce

def getLCM(a, b):
    return a * b // fractions.gcd(a, b)

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)
### BUGGY CODE ###

import sys
from math import ceil
input = sys.stdin.readline

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
ans = 0
for i in range(n):
    if xh[i][1] > 0:
        # attack
        a_num = ceil(xh[i][1] / a)
        xh[i][1] -= a_num * a
        ans += a_num
        base_x = xh[i][0]
        for j in range(i, n):
            if xh[j][0] <= base_x + 2 * d:
                xh[j][1] -= a_num * a
            else:
                break
print(ans)

### FIXED CODE ###

import sys
from math import ceil
from collections import deque

input = sys.stdin.readline

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
q = deque()
ans = 0
dam = 0
for i in range(n):
    # attack
    while len(q) > 0:
        if q[0][0] < xh[i][0]:
            dam -= q[0][1]
            q.popleft()
        else:
            break
    xh[i][1] -= dam
    if xh[i][1] > 0:
        a_num = ceil(xh[i][1] / a)
        xh[i][1] -= a_num * a
        ans += a_num
        dam += a_num * a
        q.append((xh[i][0] + 2*d, a_num * a))
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
af = tuple(zip(A, F))

v = [i * j for i, j in af]

heap = list(zip([-i for i in v], A, F))
heapify(heap)

for _ in range(K):
    a, b, c = heappop(heap)
    a = -a
    new = (a - 1) * b
    heappush(heap, (-(b - 1) * c, b - 1, c))

a, b, c = heappop(heap)
print(-a)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)
A.sort()
F.sort()
F = F[::-1]
dig = A.sum()


def judge(x):
    return dig - np.minimum(A, x // F).sum() <= K


l = -1
r = 10 ** 18 + 1

while l + 1 < r:
    test = (l + r) // 2
    if judge(test):
        r = test
    else:
        l = test

print(r)
### BUGGY CODE ###

import itertools
c=0;b=[]
for x in itertools.permutations(input()):
    if x not in b and x==x[::-1]:c+=1;b+=[x]
print(c)

### FIXED CODE ###

import collections
from math import *
s=input()
a=collections.Counter(s)
o=0
for x in a:
    if a[x]&1:
        o+=1
        if o>1:print(0);break
        a[x]-=1
else:
    b=factorial(len(s)//2)
    for x in a.values():
        b//=factorial(x//2)
    print(b)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
    b[i], c[i] = map(int, input().split())
for i in range(q):
    a=[c[i] if j == b[i] else j for j in a]
    print(sum(a))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
d=(10**5+100)*[0]
res=sum(A)
for x in A:
    d[x]+=1
for i in range(Q):
    b,c=map(int,input().split())
    res+=d[b]*(c-b)
    d[c]+=d[b]
    d[b]=0
    print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
score = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    score += A[i] * A[j]
print(score % (10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
A = list(map(int, input().split()))
score = 0
sum_A = sum(A)
for a in A[:-1]:
  sum_A -= a
  score += a * sum_A
print(score % (10**9+7))
### BUGGY CODE ###

import sys
 
S = input()
 
Q = int(input())
flag=0
 
for i in range(Q):
    r = sys.stdin.readline().strip('\n')
    if r == '1':
        S = S[::-1]
    else:
        ni, f, c = r.split()
        if f=='1':
            S = c + S
        else:
            S+=c
 
print(S)

### FIXED CODE ###

import sys

S = input()

Q = int(input())
flag=0
mae = ''
matsu = ''

for i in range(Q):
    r = sys.stdin.readline().rstrip('\n')
    if r == '1':
        flag = 1 - flag
    else:
        ni, f, c = r.split()
        if f=='1':
            if flag == 0:
                mae += c
            else:
                matsu += c
        else:
            if flag == 0:
                matsu += c
            else:
                mae += c


if flag ==0:
    print(mae[::-1]+S+matsu)
else:
    print(matsu[::-1]+S[::-1]+mae)
### BUGGY CODE ###

#!/usr/bin/env python

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

inip = 1 
for i in range(k):
    inip *= a[i]

# p = [inip]

p = [-1 for _ in range(n-k+1)]
p[0] = inip

tmp = inip
#print('inip =', inip)

for i in range(k, n): 
    s = tmp//a[i-k]*a[i]
    # p.append(s)
    p[i-k+1] = s 
    tmp = s 

# print('p =', p)

for i in range(len(p)-1):
    if p[i+1] > p[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

#!/usr/bin/env python

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

for i in range(n-k):
    if a[i] < a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())

def f(x,n):
    if x == 0:
        return n
    else:
        i = 0
        j = 0
        while 6**i <= x:
            i += 1
        while 9**j <= x:
            j += 1
        n6 = n + 1
        n9 = n + 1
        x6 = x - (6**(i-1))
        x9 = x - (9**(j-1))
        return min(f(x6,n6),f(x9,n9))

print(f(N,0))

### FIXED CODE ###

N = int(input())
list6 = [6**x for x in range(0,7) ]
list9 = [9**x for x in range(0,6) ]
result = {}

def f(x):
    if x < 6:
        return x
    elif x in result:
        return result[x] 
    else:
        max6 = max(y for y in list6 if y <= x)
        max9 = max(y for y in list9 if y <= x)
        x6 = x - max6
        x9 = x - max9
        result[x] = min(f(x6)+ 1,f(x9)+ 1)
        return result[x]

print(f(N))