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

import sys
sys.setrecursionlimit(500*500)

N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
process = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]
value = [0] * (N + 1)

for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

for que in process:
    value[que[0]] += que[1]

def dfs(s, parent, add):
    value[s] += add
    for x in graph[s]:
        if x == parent:
            continue
        dfs(x, s, value[s])

dfs(1, 0, 0)

ans =  ' '.join(map(str, value[1:]))

print(ans)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

n,q = map(int, input().split())
#長さn個のリストを入れ子にしたリストの作成：adj
adj = [[] for i in range(n)]

#adjに繋がっている要素を上流下流関わらず全て加える。
for j in range(n-1):
    a,b=map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1) 

#加算する値を合計したリストの作成
queries = [0 for i in range(n)]
for j in range(q):
    p, x = map(int, input().split())
    queries[p-1] += x

ans = [0 for i in range(n)]

#aの値，直前の値，直前のaの値
st = [(0, 0, -1)] 

#つながってる奴の一番後ろから処理していく。
#０スタート→1,2繋がってるなら2にいく。2に3が繋がってるなら次は3。
#3に繋がってるのがなければ1に戻る。
#この際，aの直前の値をタプルで保持したままリストに挿入して保管しておく。
while st:
    #stの先頭を取り出す。初期値は末尾のため-1
    l = st.pop()  
    ans[l[0]] = l[1] + queries[l[0]]
    for v in adj[l[0]]:
        if v != l[2]:
            st.append((v, ans[l[0]], l[0]))

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    uf = UnionFind(n)
    mst_edge = []
    edge.sort(key=lambda x:x[0])
    for i in range(len(edge)):
        d, v, u = edge[i]
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            mst_edge.append((v, u, d))
    
    return mst_edge  

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge_x = []
edge_y = []
for i in range(n-1):
    edge_x.append((x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    edge_y.append((y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

mst = kruskal(n, edge_x+edge_y)

print(sum([i[2] for i in mst]))

### FIXED CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))
### BUGGY CODE ###

N=int(input())

answer=0

for i in range(N):
    answer+=i
print(answer)

### FIXED CODE ###

N=int(input())

answer=0

answer+=(N**2-N)//2

print(answer)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))


import itertools
val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    for b in range(len(B_list)):
        for c in range(len(C_list)):
            if (a+1) * (b+1) * (c+1) > K:
                continue
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])

    


            


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    if a + 1 > K:
        break
    for b in range(len(B_list)):
        if b + 1 > K:
            break
        if (a+1) * (b+1) > K:
            break
            
        for c in range(len(C_list)):
            if c + 1 > K:
                break
            if (a+1) * (b+1) * (c+1) > K:
                break
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])
### BUGGY CODE ###

import heapq as h
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
q = [(-b[i],i) for i in range(n)]
h.heapify(q)
cnt = 0
while q:
  v,i = h.heappop(q)
  v *= -1
  u = b[(i-1)%n] + b[(i+1)%n]
  if v < u or a[i] >= v: continue
  t = (v-a[i])//u
  cnt += t
  b[i] -= t*u
  if b[i] > a[i]:
    h.heappush(q,(-b[i],i))
print(cnt if a==b else -1)

### FIXED CODE ###

import heapq as h
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
e6 = 10**6
q = [-b[i]*e6-i for i in range(n)]
h.heapify(q)
cnt = 0
while q:
  w = -h.heappop(q)
  v,i = w//e6, w%e6
  u = b[(i-1)%n] + b[(i+1)%n]
  if v < u or a[i] == v: continue
  elif a[i] > v: print(-1); exit(0)
  t = (v-a[i])//u
  if not t: print(-1); exit(0)
  cnt += t
  b[i] -= t*u
  if b[i] > a[i]:
    h.heappush(q,-b[i]*e6-i)
print(cnt if a==b else -1)
### BUGGY CODE ###

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

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

candidate = []
candidate.extend(A)

for j in range(M):
    b, c = map(int, input().split())
    candidate.extend([c] * b)
        
sorted_candidate = sorted(candidate, reverse=True)

print(sum(sorted_candidate[:N]))

### FIXED CODE ###

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

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

BC = []

for j in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
sorted_BC = sorted(BC, reverse=True, key=lambda item: item[1])

candidate = []
count = N
for bc in sorted_BC:
    b = bc[0]
    c = bc[1]
    if count >= 0:
        candidate.extend([c] * b)
        count = count - b
    else:
        break
    
candidate.extend(A)

print(sum(sorted(candidate, reverse=True)[:N]))
### BUGGY CODE ###

def main():
	n,k=map(int,input().split())
	a=[0]+list(map(int,input().split()))
	p=[]
	for i in range(n):
		a[i+1]+=a[i]
	for i in range(n+1):
		for j in range(i):
			p.append(a[i]-a[j])
	ans=0
	from math import log,ceil
	r=ceil(log(sum(p))+10**-3)
	for i in range(r+2,-1,-1):
		cnt=0
		for j in range(len(p)):
			if (ans+2**i)&p[j]==ans+2**i:
				cnt+=1
				if cnt==k:
					break
		if cnt==k:
			ans+=2**i
	print(ans)
if __name__ == '__main__':
	main()

### FIXED CODE ###

n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
p=[]
for i in range(n):
	a[i+1]+=a[i]
for i in range(n+1):
	for j in range(i):
		p.append(a[i]-a[j])
p.sort(reverse=True)
ans=0
from math import log,ceil
r=ceil(log(sum(p))+10**-3)
for i in range(r+3,-1,-1):
	cnt=0
	for j in range(len(p)):
		if (ans+2**i)&p[j]==ans+2**i:
			cnt+=1
		if cnt==k:
			break
	if cnt==k:
		ans+=2**i
print(ans)
### BUGGY CODE ###

import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def ceil(x):
    return int((-x)//1*(-1))


N, A, B = map(int, input().split())
hp = [int(input()) for _ in range(N)]
diff = A-B


def solve1():
    HP = sorted(hp, reverse=True)
    cnt = 0
    while HP:
        HP = list(map(lambda x: x-B, HP))
        HP[0] -= A-B
        HP = list(filter(lambda x: x > 0, HP))
        HP = sorted(HP, reverse=True)
        cnt += 1
        print(HP)
    print(cnt)


def check(x, HP):
    cnt = 0
    for i in range(N):
        if HP[i]-B*x <= 0:
            break
        else:
            cnt += ceil((HP[i]-B*x)/diff)
    #print("x->", x)
    # print(cnt)
    #print(cnt <= x)
    return cnt <= x


def solve2():
    HP = sorted(hp, reverse=True)
    mi = HP[0]//A
    ma = ceil(HP[0]/B)
    #print("mi,ma->", mi, ma)
    while mi <= ma:
        mid = (mi+ma)//2
        if check(mid, HP):
            ma = mid-1
        else:
            mi = mid+1
    print(mi)


solve2()


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def ceil(x):
    return int((-x)//1*(-1))


N, A, B = map(int, input().split())
hp = [int(input()) for _ in range(N)]
diff = A-B


def check(x, HP):
    cnt = 0
    for i in range(N):
        if HP[i]-B*x <= 0:
            break
        else:
            cnt += ceil((HP[i]-B*x)/diff)
    return cnt <= x


def solve2():
    HP = sorted(hp, reverse=True)
    mi = HP[0]//A
    ma = ceil(HP[0]/B)
    while mi <= ma:
        mid = (mi+ma)//2
        if check(mid, HP):
            ma = mid-1
        else:
            mi = mid+1
    print(mi)


solve2()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
s=list(map(int,list(input()[:-1])))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
s=list(map(int,list(input()[:-1])))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)
### BUGGY CODE ###

def binary_search_int(ok, ng, test, k, A, B):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid, k, A, B):
            ok = mid
        else:
            ng = mid
    return ok

def get_cnt(x, A, B):
    """
    a+b<=x となるようなAの要素とBの要素の組の数 (A, Bはソート済み)
    """
    cnt = 0
    L = len(B)
    for a in A:
        cnt += L-bisect_left(B, x-a)
    return cnt

def test(x, k, A, B):
    """
    場合の数が k 個(以上)となるような最小の x を探索する関数
    a+b <= x で get_cnt(x,A,B) は同じ値を返すので、最小の x は A, Bの要素の和そのものに一致する
    """
    return get_cnt(x,A,B) >= k

###########################################################

import sys
input = sys.stdin.readline
from bisect import *

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

P = []
for k in range(1,K+1):
    tmp = binary_search_int(0, 10**11,test, k, A, B)
    if tmp != 0:
        P.append(tmp)
Q = []
P.sort()
for k in range(1,K+1):
    Q.append(binary_search_int(1, 10**11,test, k, P, C))
print(*Q, sep="\n")

### FIXED CODE ###

def binary_search_int(ok, ng, test, k, A, B):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid, k, A, B):
            ok = mid
        else:
            ng = mid
    return ok

def get_cnt(x, A, B):
    """ a+b>=x となるようなAの要素とBの要素の組の数 (A, Bはソート済み)"""
    l, r = bisect_left(B, x-A[-1]), len(A)-2
    cnt = len(B) - l
    while l < len(B) and r>=0:
        if A[r]+B[l] < x:
            l += 1
        else:
            cnt += len(B) - l
            r -= 1
    return cnt

def test(x, k, A, B):
    return get_cnt(x, A, B) >= k

from bisect import *

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

P = []
for k in range(1,K+1):
    tmp = binary_search_int(0, 10**11,test, k, A, B)
    if tmp != 0:
        P.append(tmp)
Q = []
P.sort()
for k in range(1,K+1):
    Q.append(binary_search_int(1, 10**11,test, k, P, C))
print(*Q, sep="\n")
### BUGGY CODE ###

from itertools import combinations

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

comb = combinations(a, 2)
res = 0
for i, j in comb:
  res += i*j
print(res%(10**9+7))

### FIXED CODE ###

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

ans = 0
summ = sum(lst)
summ_sq = summ**2
for i in range(n):
    ans += lst[i]**2

res = (summ_sq-ans)//2
print(res % ((10**9)+7))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
if 1 not in a: 
    print(-1)
else:
    cnt = 1
    a = a[a.index(cnt)+1:]
    while cnt+1 in a:
        cnt += 1 
        a = a[a.index(cnt):]
    print(n - cnt)

### FIXED CODE ###

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

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

dp = [float("inf")]*(10**5+10)
dp[0] = 0

for i in range(N-1):
    Mi = min(K+1,N-i)
    for j in range(1,Mi):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])


### FIXED CODE ###

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

dp = [float("inf")]*(10**5+10)
dp[0] = 0

for i in range(N-1):
    Mi = min(K+1,N-i)
    for j in range(1,Mi):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])
### BUGGY CODE ###

s = list(input())
counter = 0
flag = False
while flag == False:
  for i in range(len(s) - 1):
    if s[i] == "B" and s[i+1] == "W":
      s[i] = "W"
      s[i+1] = "B"
      counter += 1
      break
  else:
    flag = True
print(counter)

### FIXED CODE ###

s = list(input())
total_l = 0
for i in range(len(s)):
  if s[i] == "W":
    total_l += i
minus = sum(list(range(s.count("W"))))
print(total_l - minus)
### BUGGY CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

x = max(a)
a.remove(x)
a.sort()
ans = 0
for i in a:
    y = cmb(x, i)
    if ans <= y:
        ans = y
    else:
        break    
    z = i
      
print(x, z)

### FIXED CODE ###

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

x = max(a)
m = x/2
a.remove(x)
a.sort()
ans = x

for i in a:
    y = abs(i - m)
    if ans >= y:
        ans = y
    else:
        break    
    z = i
      
print(x, z)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
ln = list(map(int, input().replace('W', '0 ').replace('E', '1 ').split()))
sum_min = n - 1
for i in range(n):
    sum_min = min(sum_min, sum(ln[i+1:n]) + (i - sum(ln[0:i])))

print(sum_min)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
ln = list(map(int, input().replace('W', '0 ').replace('E', '1 ').split()))

# 先頭だけ先に計算（do-while相当）
w_sum = 0                           # 西側で振り返る人
sum_min = e_sum = sum(ln) - ln[0]   # 東側で振り返る人

for i in range(1, n-1):
    #sum_min = min(sum_min, sum(ln[i+1:n]) + (i - sum(ln[0:i])))
    w_sum += 1 if ln[i-1] == 0 else 0
    e_sum -= ln[i]
    sum_min = min(sum_min, w_sum + e_sum)

# 末尾も個別に計算
else:
    w_sum += 1 if ln[n-1] == 0 else 0
    sum_min = min(sum_min, w_sum)


print(sum_min)
### BUGGY CODE ###

n = input()
R = [input()] 
Rmin = 0
maxdif = -999999999
for i in xrange(n-1):
    Rt = input()
    for j in xrange(Rmin, len(R)):
        if (Rt - R[j]) > maxdif:
            maxdif = Rt - R[j]
    if Rt < R[Rmin]:
        Rmin = i + 1
    R.append(Rt)

print maxdif

### FIXED CODE ###

n = input()
R = [input() for i in xrange(n)]

Rmin = n
maxdif = R[1] - R[0]

while Rmin > 0:
    tRmin = R.index(min(R[0:Rmin]))
    Rmax = R.index(max(R[tRmin:Rmin]))
    if tRmin == Rmax:
        if tRmin == n-1:
            tRmin-=1
        elif tRmin < n-1:
            Rmax = tRmin + 1
    Rmin = tRmin
    if (R[Rmax] - R[Rmin]) > maxdif:
        maxdif = R[Rmax] - R[Rmin]

print maxdif
### BUGGY CODE ###

import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    # print(d)
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                if d[bi] and d[bi][-1] <= m-i:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import heapq
def main():

    N, M = map(int, input().split())
    task = []
    for _ in range(N):
        A, B = map(int, input().split())
        task.append([A, B])
    task.sort()

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

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

n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)
ans=0
for c in range(n-2):
    for a in range(n-2):
        flag=0
        b=c+1
        while flag!=1 and b<n-1-a:
            if l[c]<l[b]+l[n-1-a]:
                ans+=1
                b+=1
            else:
                flag=1
print(ans)


### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)
ans=0
for c in range(n-2):
    for b in range(c+1,n-1):
        flag=0
        if l[c]-l[b]+1>l[b+1]:
            flag=1
        elif l[c]-l[b]+1<=l[n-1]:
            ans+=(n-1-b)
            flag=1
        m=n-1
        h=b+1
        while flag!=1:
            x=(h+m)//2
            bef=x
            if l[x]>l[c]-l[b]+1:
                h=x
                x=(m+h)//2
            elif l[x]<l[c]-l[b]+1:
                m=x
                x=(m+h)//2
            else:
                if x==n-1:
                    ans+=(x-b)
                    break
                if l[x+1]==l[c]-l[b]+1:
                    h=x
                    x=(m+h)//2
                else:
                    ans+=(x-b)
                    break
            if bef==x:
                ans+=(x-b)
                break
print(ans)
### BUGGY CODE ###

A,B,N = map(int,input().split())
score = 0
for i in range(N+1):
    temp = int(A*i/B)-A*int(i/B)
    score = max(temp, score)
print(score)

### FIXED CODE ###

A,B,N = map(int,input().split())
score = 0
if N>=B:
    x = B-1
else:
    x = N

score = int(A*x/B)-A*int(x/B)
print(score)
### BUGGY CODE ###

H, W, M = map(int, input().split())
 
h = [0] * H
w = [0] * W
Mem = []
for _ in range(M):
  i, j = map(int, input().split())
  Mem.append((i, j))
  h[i-1] += 1
  w[j-1] += 1

maxh = max(h)
maxw = max(w)

listh = [i for i, v in enumerate(h, 1) if v == maxh]
listw = [j for j, v in enumerate(w, 1) if v == maxw]

b = [(i, j) for i in listh for j in listw if (i, j) not in Mem]

if len(b):
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)

### FIXED CODE ###

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50



def run():
    N = int(input())
    lasts = defaultdict(lambda:[])
    lengths = set()
    S = []
    for i in range(N):
        s = input()
        S.append(s)
        lasts[s[1:]].append(i)
        lengths.add(len(s)-1)
    #print(lasts)
    #print(lengths)
    ans = 0
    for s in S:
        for l in lengths:
            if l == 0:
                if '' in lasts.keys():
                    for k in lasts['']:
                        if S[k][0] in s:
                            ans += 1
                            #print(s, l, S[k])
            else:
                if s[-l:] in lasts.keys():
                    for k in lasts[s[-l:]]:
                        if S[k][0] in s[:-l]:
                            ans += 1
                            #print(s, l, S[k])

    print(ans-N)



    

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50



def run():
    N = int(input())
    lasts = defaultdict(lambda:[])
    lengths = set()
    S = []
    for i in range(N):
        s = input()
        S.append(s)
        lasts[s[1:]].append(i)
        lengths.add(len(s)-1)
    #print(lasts)
    #print(lengths)
    ans = 0
    for s in S:
        for l in lengths:
            if l == 0:
                if '' in lasts.keys():
                    for k in lasts['']:
                        if S[k][0] in s:
                            ans += 1
                            #print(s, l, S[k])
            else:
                if s[-l:] in lasts.keys():
                    for k in lasts[s[-l:]]:
                        if S[k][0] in s[:-l]:
                            ans += 1
                            #print(s, l, S[k])

    print(ans-N)



    

if __name__ == "__main__":
    run()