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

# 26

import sys

sys.setrecursionlimit(10**9)

n, q = map(int, input().split())
ans_l = [0] * n
graph = [[] for x in range(n)]

def dfs(v, p=-1):
    if p >= 0:
        ans_l[v] += ans_l[p]
    for i in range(len(graph[v])):
        _v = graph[v][i]
        if _v != p:
            dfs(_v, v)
        
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
for j in range(q):
    p, x = map(int, input().split())
    ans_l[p-1] += x
    
dfs(0)

print(*ans_l)

### FIXED CODE ###

# 26

import sys

sys.setrecursionlimit(10**9)

n, q = map(int, input().split())
ans_l = [0] * n
graph = [[] for x in range(n)]

def dfs(v, p=-1):
    if p >= 0:
        ans_l[v] += ans_l[p]
    for i in range(len(graph[v])):
        _v = graph[v][i]
        if _v != p:
            dfs(_v, v)
        
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
for j in range(q):
    p, x = map(int, input().split())
    ans_l[p-1] += x
    
dfs(0)

print(*ans_l)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [tuple(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(dp[W])


### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: (x[0],x[1]))
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))
### BUGGY CODE ###

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

while N>=K:
  N = N - K

while N!=0:
  if N>=abs(N-K):
    N = abs(N-K)
  elif N==0:
    break
  else:
    break            
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
if N>=K:
  N = N%K

while N!=0:
  if N>=abs(N-K):
    N = abs(N-K)
  elif N==0:
    break  
  else:
    break
print(N)
### BUGGY CODE ###

import itertools

def coin_change(coins, val):
    num = 1
    while True:
        for subset in itertools.combinations_with_replacement(coins, num):
            if sum(subset) == val:
                return num
        num += 1

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

c = list(map(int, input().split()))

ans = coin_change(c, n)

print(ans)

### FIXED CODE ###

def coin_change(coins, payment):
    T = [0] + [50001] * payment
    for c in coins:
        for i, t in enumerate(zip(T[c:], T), start=c):
            a, b = t
            T[i] = min(a, b + 1)
    return T[payment]

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

c = list(map(int, input().split()))

ans = coin_change(c, n)

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

#coding: utf-8
def main(N, K, h):
    dp = [float("inf") for _ in range(N)]
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)])
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

s = input()
while "ST" in s:
	s = s.replace("ST", "", 100000)
print(len(s))

### FIXED CODE ###

S = input()
cs = 0
ans = 0
for i in range(len(S)):
  si = S[i]
  if si == 'T' and cs > 0:
    cs -= 1
    ans += 2
  elif si == 'S':
    cs += 1
    
print(len(S)-ans)
### BUGGY CODE ###

# 有効グラフ上で、近道に当たる点はすべて余計な辺
# ある点に入ってくる最も距離が長い辺のみが有効となる
# DFSで、あとから入ってきたときにその親を記録すればよいのでは。
# 最後に残ったものを出力する
# 入力のあった頂点を記録することで、入力の無かった頂点を根とみなせる

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
grandparent = set(range(N))
for i in range(N - 1 + M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  grandparent -= {b - 1}

start = list(grandparent)[0]
from collections import deque

D = -1000
ans = [D for i in range(N)]

# 頂点、親
q = deque([[start, -1]])
while q:
  v, parent = q.popleft()
  ans[v] = parent
  for child in G[v]:
    q.append([child, v])
    
for a in ans:
  print(a + 1)

### FIXED CODE ###

# トポロジカルソート

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
revG = [[] for i in range(N)]
# ある頂点に対する入次数を記録
indegree = [0 for i in range(N)]

for i in range(N - 1 + M):
  u,v = map(int,readline().split())
  G[u - 1].append(v - 1)
  revG[v - 1].append(u - 1)
  indegree[v - 1] += 1

# トポロジカルソートを格納する
res = []

# 入り次数が0になった頂点を高速に発見するため、隣接する頂点をキューで管理
from collections import deque
q = deque()
for i in range(len(indegree)):
  if indegree[i] == 0:
    q.append(i)

while q:
  # キューの先頭の頂点を取り出す
  v = q.popleft()
  
  # その頂点と隣接する頂点の入次数を減らし、0になったらキューに追加
  for child in G[v]:
    indegree[child] -= 1
    if indegree[child] == 0:
      q.append(child)
      
  # 入り次数が0で且つ隣接する頂点が処理済みとなった頂点をソート配列に追加する
  res.append(v)
  
# インデックスと頂点番号を逆転させたものを作成する
inds = [-1 for i in range(N)]
for i in range(len(res)):
  inds[res[i]] = i
  
# print(inds)
for i in range(len(revG)):
  ans = -1
  maxv = -1
  for parent in revG[i]:
#    print("i",i,"に対する親",parent)
    if inds[parent] > maxv:
      maxv = inds[parent]
      ans = parent
  print(ans + 1)
### BUGGY CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
from collections import deque
squares = deque()
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.appendleft(square)
ans = float('inf')
pairs = (-10**9,10**9,-10**9,10**9)
while squares:
    x1,x2,y1,y2 = squares.popleft()
    if x1==x2 or y1==y2:
        continue
    if x2-x1>=pairs[1]-pairs[0] and y2-y1>= pairs[3]-pairs[2]:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
        pairs = (x1,x2,y1,y2)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)
### BUGGY CODE ###

import math
 
k = int(input())
ans = 0
 
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(math.gcd(a, b), c)
 
print(ans)

### FIXED CODE ###

import math
 
k = int(input())
ans = 0
 
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a,b)
        for c in range(1, k+1):
            ans += math.gcd(tmp, c)
 
print(ans)
### BUGGY CODE ###

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

s = [1+0.5*(i-1) for i in range(1,max(p)+1)]

ma = 0
for i in range(n-k+1):
    ans=0
    for j in range(k):
        ans += s[p[i+j]-1]
    if(ma<ans):
        ma = ans
    
print(ma)

### FIXED CODE ###

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

s = [1+0.5*(i-1) for i in range(1,max(p)+1)]

q = [0]
c = 0
for i in p:
    c += s[i-1]
    q.append(c)

ma = 0
for i in range(k,n+1):
    ans = q[i]-q[i-k]
    if(ma<ans):
        ma = ans
    
print(ma)
### BUGGY CODE ###

n=int(input())

for i in range(1,n+1):
  count = 0
  for x in range(1,101):
    for y in range(1,101):
      for z in range(1,101):
        fn = (x+y)**2 + (y+z)**2 + (z+x)**2
        if fn > 2*i:
          break
        if fn == 2*i:
          count += 1
  print(count)

### FIXED CODE ###

n=int(input())

result = [0] * (n+1)
for x in range(1,99):
  for y in range(1,99):
    for z in range(1,99):
      fn = x*x + y*y + z*z + x*y + y*z + z*x
      if fn > n:
        break
      result[fn] += 1

for i in range(1,n+1):
  print(result[i])
### BUGGY CODE ###

s=str(input())
k=int(input())

lista=[]
for i in range(26):
	lista.append(chr(ord('a') + i))
	
#print(lista)

s_list=list(s)
len_s=len(list(s))
temp1=k
temp2=0
for i in range(len_s-1):
	if (123-ord(s_list[i])<=temp1)&(temp1>=0):
		temp1=temp1-(123-ord(s_list[i]))
		s_list[i]="a"
if temp1!=0:
#	print(temp1)
	temp2=temp1%26+ord(s_list[-1])
	if temp2>122:
		temp2=temp2-122+96
	s_list[-1]=chr(temp2)
#print(temp2)
#print(str(s_list))
row=""
for i in range(len(s_list)):
	row+=s_list[i]
print(row)
		

		
	
	
	


### FIXED CODE ###

s=str(input())
k=int(input())

lista=[]
for i in range(26):
	lista.append(chr(ord('a') + i))
	
#print(lista)

s_list=list(s)
len_s=len(list(s))
temp1=k
temp2=0
for i in range(len_s):
	if (123-ord(s_list[i])<=temp1)and (s_list[i] != 'a'):
		temp1=temp1-(123-ord(s_list[i]))
		s_list[i]="a"
if temp1!=0:
#	print(temp1)
	temp2=temp1%26+ord(s_list[-1])
	if temp2>122:
		temp2=temp2-122+96
	s_list[-1]=chr(temp2)
#print(temp2)
#print(str(s_list))

for i in range(len(s_list)):
	print(s_list[i],end="")
print()
### BUGGY CODE ###

n,t,a,*u=map(int,open(0).read().split())
for u,b in zip(u[::2],u[1::2]):
    v,c=u,b
    while v<t or c<a:
        v+=u
        c+=b
    t,a=v,c
print(t+a)

### FIXED CODE ###

n,t,a,*u=map(int,open(0).read().split())
for u,b in zip(u[::2],u[1::2]):
    x=0-min(-t//u,-a//b)
    t,a=u*x,b*x
print(t+a)
### BUGGY CODE ###

import queue

h,w=map(int,input().split())

ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

ch-=1
cw-=1
dh-=1
dw-=1
#c->d

s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while not q.empty():
  sth,stw=q.get()
  qi=queue.Queue()
  qi.put([sth,stw])
  ph=0
  pw=0
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]==0:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]==".":
        q.put([warph,warpw])
        seen[warph][warpw]=1
        distance[warph][warpw]=distance[i][j]+1

if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[dh][dw])


### FIXED CODE ###

import queue

h,w=map(int,input().split())

ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

ch-=1
cw-=1
dh-=1
dw-=1
#c->d

s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()#start point of each domain

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while (not q.empty()) and distance[dh][dw]==10**7:
  sth,stw=q.get()
  qi=queue.Queue()#BFS
  qi.put([sth,stw])
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]!=1:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]=="." and seen[warph][warpw]==0:
        q.put([warph,warpw])
        seen[warph][warpw]=2
        distance[warph][warpw]=distance[i][j]+1



if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[dh][dw])
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0

for i in range(N):
    if min(P[:i + 1]) >= P[i]:
        count += 1

print(count)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0
comp = 2 * (10**5)

for i in range(N):
    if comp >= P[i]:
        count += 1
        comp = P[i]

print(count)
### BUGGY CODE ###

s=list(input())
s=[int(i) for i in s]
last_mod=0
from collections import defaultdict
c=defaultdict(int)
c[0]+=1
for i in range(len(s)):
    now=(s[-1-i]*(10**i))%2019
    c[(last_mod+now)%2019]+=1
    last_mod=(last_mod+now)%2019
ans=0
for k in c.keys():
    ans+=c[k]*(c[k]-1)//2
print(ans)

### FIXED CODE ###

s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n-1, 0, -1):
  ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n-1)*n//2
print(ans)
### BUGGY CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import time
time.sleep(2)
P,Q,R = map(int,input().split())
print(min(P+Q,min(Q+R,R+P)))

### FIXED CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python

P,Q,R = map(int,input().split())
print(min(P+Q,min(Q+R,R+P)))
### BUGGY CODE ###

N = int(input())
S =[]
for n in range(N):
    s = input()
    S.append(s[0])
NAME = ["M","A","R","C","H"]
from itertools import permutations
pattern = list(permutations(NAME,3))
LEN = len(S)
cnt=0
for s1 in range(LEN-2):
    for s2 in range(s1+1,LEN-1):
        for s3 in range(s2+1,LEN):
            if (S[s1],S[s2],S[s3]) in pattern:
                cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
S =[]
for n in range(N):
    s = input()
    S.append(s[0])
S=sorted(S)
NAME = sorted(["M","A","R","C","H"])
from itertools import combinations
from collections import Counter
pattern = list(combinations(NAME,3))
LEN = len(S)
cnt=0
Counter_S =Counter(S)
cnt = 0
for p in pattern:
    cnt +=(Counter_S[p[0]] * Counter_S[p[1]] * Counter_S[p[2]])
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    s = input()

    rgb = {'r':[], 'g':[], 'b':[]}

    for i in range(n):
        if s[i] == 'R':
            rgb.get('r').append(i+1)
        elif s[i] == 'G':
            rgb.get('g').append(i+1)
        elif s[i] == 'B':
            rgb.get('b').append(i+1)

    count = 0
    for r_num in rgb.get('r'):
        for g_num in rgb.get('g'):
            for b_num in rgb.get('b'):
                i, j, k = tuple(sorted([r_num, g_num, b_num]))
                if j - i != k - j:
                    count += 1

    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    s = input()

    r = []
    g = []
    b = []

    for i in range(n):
        if s[i] == 'R':
            r.append(i+1)
        elif s[i] == 'G':
            g.append(i+1)
        elif s[i] == 'B':
            b.append(i+1)

    count = len(r) * len(g) * len(b)
    for r_num in r:
        for g_num in g:
            dif = abs(r_num - g_num)
            i, j = tuple(sorted([r_num, g_num]))

            if i - dif > 0:
                if s[i - dif - 1] == 'B':
                    count -= 1
            if j + dif <= n:
                if s[j + dif - 1] == 'B':
                    count -= 1
            if dif % 2 == 0:
                if s [i + dif // 2 - 1] == 'B':
                    count -= 1

    print(count)

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

n = int(input())

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

a = 1

for i in b:
  a = a * i

if a - 1000000000000000000 > 0:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n = int(input())

l = list(map(int, input().split()))
l.sort()

if l[0] == 0:
  print(0)
  exit()
res = 1

for i in l:
  res *= i
  if res > 10 **18:
    print(-1)
    exit()
print(res)
### BUGGY CODE ###

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

a2 = 0
for i in range(2,n):
    a2 ^= a[i]

ans = -1
for i in range(a[0]):
    a0 = (a[0] - i) ^ (a[1] + i)
    if a0 ^ a2 == 0:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

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

K = 43

#
A = Arr[0]
B = Arr[1]

S = A + B
X = 0
for i in range(2, len(Arr)):
    X ^= Arr[i]

# print(S, X)

# 次を満たすa, b が見つかるか？
#  a+b=S, a^b=X, a<=A

# 桁DP : 桁を一つずつ決めていくようなDP
# dp[今の桁数 = 0:42][繰り上がりがあるか = 0,1][今までがA以下かどうか 0=以下、1=より大きい] = 最大値
# 値は最大値。満たすものがなければ -1
dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]

dp[0][0][0] = 0  # 最初

v = 1
for i in range(K - 1):  # 桁数
    cx = X & 1  # current X
    cs = S & 1  # current S
    ca = A & 1  # current A
    for j in range(2):  # 繰り上がりある／ない
        for k in range(2):  # 今までの範囲が A 以下かどうか
            if dp[i][j][k] == -1:  #
                continue

            for na in range(2):
                for nb in range(2):
                    ni = i + 1
                    nj = 0
                    nk = k
                    if na ^ nb != cx:  # a ^ b = A か？
                        continue

                    ns = na + nb + j
                    if ns % 2 != cs:  # a + b = S か？
                        continue

                    # ここで遷移は確定

                    if ns >= 2:  # 繰り上がり処理
                        nj = 1

                    if ca < na:
                        nk = 1
                    elif ca == na:
                        nk = k
                    else:
                        nk = 0

                    dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | (v * na))

    X >>= 1
    S >>= 1
    A >>= 1
    v <<= 1
    # print(v)

a = dp[K - 1][0][0]
if a == -1 or a == 0:
    print(-1)
else:
    print(Arr[0] - a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N= int(input())
A= list(map(int,input().split(' ')))
 
ans = 0
for i in range(len(A)-1):
  ans += A[i] * sum(A[i+1:])

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


### FIXED CODE ###

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

mod = 10**9+7
ans = 0
cs = 0
for i in range(N-1, -1, -1):
  ans = (ans+A[i]*cs) % mod
  cs = (cs+A[i]) % mod

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

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

checked = [[True for i in range(N)] for j in range(N)]
def ver(i, j, length):
    for f in range(length):
        if S[i+f] != S[j+f]: return False
    return True

def check(length):
    found = False
    for i in range(N):
        for j in range(i+length, N-length+1):
            if checked[i][j]:
                res = ver(i, j, length)
                if res:
                    found = True
                else:
                    checked[i][j] = False
    return found
            

for i in range(1, N):
    if not check(i):
        print(i - 1)
        break


### FIXED CODE ###

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

def z_advanced(s):
    # Taken from https://ivanyu.me/blog/2013/10/15/z-algorithm/
    """An advanced computation of Z-values of a string."""
 
    Z = [0] * len(s)
    Z[0] = len(s)
 
    rt = 0
    lt = 0
 
    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.
 
            p = k - lt  # Pair index.
            right_part_len = rt - k + 1
 
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k
 
                lt = k
                rt = i - 1
    return Z

best = 0
for i in range(N):
    lst = z_advanced(S[i:])
    for j, longest in enumerate(lst):
        best = max(best, min(j, longest))
print(best)
### BUGGY CODE ###

X = int(input())

c = []
for i in range(-(X+1), X+1):
    if i != 0 and X % i == 0:
        c.append([i, X//i])

for x1, x2 in c:
    for b in range(-10000, 10000):
        if b != 0:
            if (x1+b)**4 + ((x1+b)**3)*b + ((x1+b)**2)*(b**2) + (x1+b)*(b**3) + b**4 == x2:
                print(x1+b, b)
                break

### FIXED CODE ###

X = int(input())

c = []
for i in range(1, int((X+1)**(1/2))+1):
    if i != 0 and X % i == 0:
        c.append([i, X//i])

for x1, x2 in c:
    for b in range(-1000, 1000):
        if b != 0:
            if (x1+b)**3 * (2*b+x1) + (b**2) * (x1**2 + 3*x1*b+3*(b**2)) == x2:
                print(x1+b, b)
                break
### BUGGY CODE ###

import numpy as np

n = int(input())
moji = [list(map(str,input())) for index in range(n)]
count = int(0)

for index in range(n):
  moji[index].sort()

for index in range(n):
  for index2 in range(index+1,n):
    if moji[index]==moji[index2]:
      count+=1

print(count)

### FIXED CODE ###

import numpy as np
import collections

n = int(input())
moji = [list(map(str,input())) for index in range(n)]
count = 0

for index in range(n):
  moji[index].sort()
  moji[index] = "".join(moji[index])

moji.sort()

for index in collections.Counter(moji).values():
  n = index - 1
  count += n*(1+n)/2

print(int(count))