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

from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

for _ in range(n-1):
  a,b,c = map(int, input().split())
  graph[a-1].append([b-1,c])
  graph[b-1].append([a-1,c])

q, k = map(int, input().split())
k -= 1
for _ in range(q):
  x, y = map(int, input().split())
  print( solve(graph, n, x-1, k) + solve(graph, n, k, y-1))

### FIXED CODE ###

from collections import defaultdict, deque
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

for _ in range(n-1):
  a,b,c = map(int, input().split())
  graph[a-1].append([b-1,c])
  graph[b-1].append([a-1,c])

q, k = map(int, input().split())
k -= 1

l = [0 for _ in range(n)]
queue = deque()
queue.append(k)
while len(queue) > 0:
  a = queue.pop()
  for b, c in graph[a]:
    if l[b] == 0:
      l[b] = l[a] + c
      queue.append(b)

for _ in range(q):
  x, y = map(int, input().split())
  print( l[x-1] + l[y-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Ma, Mb = map(int, input().split())
l = [[0] * 3 for i in range(N)]
for i in range(N):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

def dfs(cur, a, b, c):
    mn = INF
    if b != 0 and a / b == Ma / Mb:
        mn = min(c, mn)
    if cur == N:
        return mn
    mn = min(dfs(cur+1, a+l[cur][0], b+l[cur][1], c+l[cur][2]), mn)
    mn = min(dfs(cur+1, a, b, c), mn)
    return mn

ans = dfs(0, 0, 0, 0)
if ans == INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc054/editorial.pdf
・3次元DP
・送るDP
"""
 
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N, Ma, Mb = map(int, input().split())
l = [[0] * 3 for i in range(N)]
for i in range(N):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

# 不可能な組み合わせは0とは区別するのでINF初期化
dp = [[[INF] * 401  for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(401):
        for k in range(401):
            # あり得ない組み合わせの時は送らない
            if dp[i][j][k] == INF: continue
            dp[i+1][j][k] = min(dp[i][j][k], dp[i+1][j][k])
            dp[i+1][j+l[i][0]][k+l[i][1]] = min(dp[i][j][k] + l[i][2], dp[i+1][j+l[i][0]][k+l[i][1]])

ans = INF
for j in range(1, 401):
    for k in range(1, 401):
        # j/k == Ma/Mb だと分母0が心配なので
        if j * Mb == k * Ma:
            ans = min(dp[N][j][k], ans)

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())		# 5 7
S = input()

#print(N,Q,S)

for q in range(1,Q+1):
	ans=0
	l, r = map(int, input().split())		# 5 7
	s = S[l-1:r]
	#print(l,r,s, len(s))
	
	x=-1
	for i in range(len(s)):
		if i<x: continue
		x = s.find("AC",i)
		if x>=0:
			ans += 1
			x+=2
		#print(s,i,x,ans)

	print(ans)
	

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

C=[0]*(N)
c=0
for i in range(len(S)-1):
  if S[i:i+2]=="AC": c += 1
  C[i] = c

#print(C)

for q in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1

  ans = C[r-1] - C[l-1]
  print(ans)
### BUGGY CODE ###

n = int(input())

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

for i in range(n):
  if i == 0:
    b = c[i]
  else:
    b = b*c[i]
if b>1000000000000000000:
  b = -1
print(b)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
if min(a)==0:
    print(0)
else:
    s=1
    for i in range(len(a)):
       s=s*a[i]
       if s>10**18:
           print(-1)
           break
    else:
        print(s)
### BUGGY CODE ###

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


point = 1
for i in range(k):
    point *= A[i]
temp = 1

for i in range(k, n):
    for j in range(i-k+1, i+1):
        temp *= A[j]
    if temp > point:
        print("Yes")
        point = temp
        temp = 1
    else:
        print("No")
        point = temp
        temp = 1


### FIXED CODE ###

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

for i in range(k,n):
    if A[i] > A[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter
n=input()
count=0
for i in range(357,int(n)+1,2):
    c=Counter(str(i))
    if len(c.keys())==3:
        if c['3'] and c['5'] and c['7']:
            count +=1
print(count)


### FIXED CODE ###

n = (int)(input())

def f(s):
    ans = 0
    if (int)(s) > n:
        return 0
    for c in '753':
        num = (str)(s+c)
        if (int)(num) <= n:
            if num.count('3')and num.count('5') and num.count('7'):
                ans += 1
            ans += f(num)
    return ans
print(f('0'))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0

for r in range(2, N - 1):
    # 左のしゃくとり
    P, Q = P2, Q2 = -1, -1
    p = 0
    q = 1
    while True:
        P2, Q2 = P, Q
        P = SUM[q - 1]
        Q = SUM[r - 1] - SUM[q - 1]
        if P < Q and q < r:
            q += 1
        else:
            break
    left_min, left_max = min(P, Q), max(P, Q)
    if P2 != -1:
        if abs(Q - P) > abs(Q2 - P2):
            left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右のしゃくとり
    R, S = R2, S2 = -1, -1
    s = r + 1
    while True:
        R2, S2 = R, S
        R = SUM[s - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[s - 1]
        if R < S and s < N - 1:
            s += 1
        else:
            break
    right_min, right_max = min(R, S), max(R, S)
    if R2 != -1:
        if abs(R - S) > abs(R2 - S2):
            right_min, right_max = min(R2, S2), max(R2, S2)

    # print(p, q, r, s)
    # print(P, Q, R, S)
    # print(P2, Q2, R2, S2)
    # print("----------")

    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0
p = 0
q = 1
r = N // 2
s = r + 1
for r in range(2, N - 1):
    # 左
    P1, Q1 = P2, Q2 = -1, -1
    low, high = 1, r - 1
    while low + 1 < high:
        mid = (low + high) // 2
        P = SUM[mid - 1]
        Q = SUM[r - 1] - SUM[mid - 1]
        if P < Q:
            low = mid
        else:
            high = mid
    P1, Q1 = SUM[low - 1], SUM[r - 1] - SUM[low - 1]
    P2, Q2 = SUM[high - 1], SUM[r - 1] - SUM[high - 1]
    left_min, left_max = min(P1, Q1), max(P1, Q1)
    if abs(Q1 - P1) > abs(Q2 - P2):
        left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右
    R1, S1 = R2, S2 = -1, -1
    low, high = r + 1, N - 1
    while low + 1 < high:
        mid = (low + high) // 2
        R = SUM[mid - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[mid - 1]
        if R < S:
            low = mid
        else:
            high = mid
    R1, S1 = SUM[low - 1] - SUM[r - 1], SUM[N - 1] - SUM[low - 1]
    R2, S2 = SUM[high - 1] - SUM[r - 1], SUM[N - 1] - SUM[high - 1]
    right_min, right_max = min(R1, S1), max(R1, S1)
    if abs(R1 - S1) > abs(R2 - S2):
        right_min, right_max = min(R2, S2), max(R2, S2)

    # print(P1, Q1, R1, S1, sum([P1, Q1, R1, S1]), sum(A))
    # print(P2, Q2, R2, S2, sum([P2, Q2, R2, S2]), sum(A))
    # print("--------")
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

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

N,M = map(int, input().split())
A = [int(input()) for i in range(M)]

dp = [0]*(N+1)
dp[0] = 1

for next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = dp[next-1] + dp[next-2]

print(dp[N]%1000000007)

### FIXED CODE ###

N,M = map(int, input().split())
A = set([int(input()) for i in range(M)])

dp = [0]*(N+1)
dp[0] = 1

for next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = (dp[next-1] + dp[next-2])%1000000007

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

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a: l = x * l // gcd(x, l)
for x in a:
  res += l // x
  res %= mod
print(res)

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a:
  l = x * l // gcd(x, l)
l %= mod
for x in a:
  res += l * pow(x, mod - 2, mod)
  res %= mod
print(res)
### BUGGY CODE ###

def judge(item,tmp):
  for i in tmp:
    if i == item:
      return False
  return True

n = int(input())
s = [input() for _ in range(n)]


tmp = []
for i in s:
  if judge(i,tmp):
  	tmp.append(i)
    
print(len(tmp))

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
print(len(set(s)))
### BUGGY CODE ###

MOD = int(1e9) + 7


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    sortA = sorted(A)
    sortB = sorted(B)
    for i in range(1, N):
        if sortA[i] == sortA[i-1]:
            print(0)
            return
    for j in range(1, M):
        if sortB[j] == sortB[j-1]:
            print(0)
            return
    retval = 1
    for num in range(N*M, 0, -1):
        icandidates = 0
        jcandidates = 0
        just = 1
        for i in range(N):
            if num == A[i]:
                icandidates = 1
                just = 0
                break
            if num <= A[i]:
                icandidates += 1
        for j in range(M):
            if num == B[j]:
                jcandidates = 1
                just = 0
                break
            if num <= B[j]:
                jcandidates += 1
        retval *= icandidates * jcandidates - (N*M - num) * just
        retval %= MOD

    print(retval)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = int(1e9) + 7


def binsearch(num, ary):
    left = 0
    right = len(ary)
    while left < right:
        center = (left + right) // 2
        if num <= ary[center]:
            left = center + 1
        else:
            right = center
    return left


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    sortA = sorted(A, reverse=True)
    sortB = sorted(B, reverse=True)
    for i in range(1, N):
        if sortA[i] == sortA[i-1]:
            print(0)
            return
    for j in range(1, M):
        if sortB[j] == sortB[j-1]:
            print(0)
            return
    retval = 1
    for num in range(N*M, 0, -1):
        just = 1
        icandidates = binsearch(num, sortA)
        jcandidates = binsearch(num, sortB)
        if icandidates >= 1 and sortA[icandidates-1] == num:
            icandidates = 1
            just = 0
        if jcandidates >= 1 and sortB[jcandidates-1] == num:
            jcandidates = 1
            just = 0
#        print(icandidates, jcandidates, sortA, num)

        retval *= icandidates * jcandidates - (N*M - num) * just
        retval %= MOD

    print(retval)


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

import sys


def isprime(x):
    # 素数判定
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


def solve(l, r, primelist, primelist2):
    res = 0
    for i in range(l, r + 1, 2):
        if primelist[i] and primelist2[i]:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [False] * (10 ** 5 + 10)
    primelist2 = [False] * (10 ** 5 + 10)
    primelist[2] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if isprime(i):
            primelist[i] = True
        if isprime((i + 1) // 2):
            primelist2[i] = True
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primelist, primelist2))


if __name__ == "__main__":
    main()


### FIXED CODE ###

MAX = 10 ** 5 + 1
f = [True] * (MAX)
c = [0] * (MAX + 1)
for i in range(2, MAX):
    if f[i]:
        for j in range(i + i, MAX, i):
            f[j] = False
for i in range(3, MAX, 2):
    if f[i] and f[(i + 1) // 2]:
        c[i] += 1
for i in range(3, MAX):
    c[i] += c[i - 1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l - 1])
### BUGGY CODE ###

import sys,heapq
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
ddprint("q " + str(q))
for i in range(1,q):
    #ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            aa = -heapq.heappushpop(tl,-a)
            suml += a - aa
            if aa<root:
                aa,root = root,aa
            heapq.heappush(tr,aa)
            sumr += aa
            nr += 1
        else:
            aa = heapq.heappushpop(tr,a)
            sumr += a - aa
            if aa>root:
                aa,root = root,aa
            heapq.heappush(tl,-aa)
            suml += aa
            nl += 1
        #ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        #ddprint(tl)
        #ddprint(tr)


### FIXED CODE ###

import heapq
#printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
#inm   = lambda:      map(int, input().split())
DBG = True  and False
#def ddprint(x):
#  if DBG:
#    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
#ddprint("q " + str(q))
for i in range(1,q):
    #ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            aa = -heapq.heappushpop(tl,-a)
            suml += a - aa
            if aa<root:
                aa,root = root,aa
            heapq.heappush(tr,aa)
            sumr += aa
            nr += 1
        else:
            aa = heapq.heappushpop(tr,a)
            sumr += a - aa
            if aa>root:
                aa,root = root,aa
            heapq.heappush(tl,-aa)
            suml += aa
            nl += 1
        #ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        #ddprint(tl)
        #ddprint(tr)
### BUGGY CODE ###

import sys
from collections import deque

# 初期化
n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
D = [sys.maxsize for _ in range(n_V)]

# 入力
for i in range(n_E):
    v, e, d = map(int, input().split())
    E[v].append((e, d))

#　各頂点への最短距離を求める処理
D[r] = 0
queue = deque([r])
visited = set()

while len(queue) != 0:
    current = queue.popleft()
    visited.add(current)

    for e, d in E[current]:
        if D[e] > D[current] + d:
            D[e] = D[current] + d
            if e in visited: visited.remove(e)

        if e not in queue and e not in visited:
            queue.append(e)

# 出力
for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)



### FIXED CODE ###

import sys
from heapq import heappush
from heapq import heappop


# 入力
n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
for i in range(n_E):
    v, e, c = map(int, input().split())
    E[v].append((e, c))


# 初期化
D = [sys.maxsize for _ in range(n_V)]
D[r] = 0

h = []
heappush(h, (D[r], r))


#　各頂点への最短距離を求める処理
while len(h) != 0:
    _, index = heappop(h)

    for e, c in E[index]:
        d = D[index] + c
        if D[e] > d:
            D[e] = d
            heappush(h, (d, e))


# 出力
for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        exit()

    print(v2)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        exit()
    
    return l[v2]==l[v1]


left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2
    v = get(left, mid)
    if (v==True and (mid-left)%2) or (v==False and (mid-left)%2==0):
        right = m
    else:
        left = m

    

### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

s = list(map(int, list(input())))
ls = len(s)
while True:
    f = False
    for i in range(len(s)-1):
        if (s[i] ==0 and s[i+1] ==1) or (s[i] ==1 and s[i+1] ==0):
            del s[i:i+2]
            f = True
            break
    if f == False:
        break
print(ls-len(s))

### FIXED CODE ###

s = list(input())
print(min(s.count('1'), s.count('0'))*2)
### BUGGY CODE ###

n, m = map(int, input().split())
br = [int(input()) for i in range(m)]

dp = [0 for _ in range(n + 1)]

dp[0] = 1
if 1 not in br:
    dp[1] = 1
for i in range(2, n + 1):
    if i in br:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] = dp[i] % (10 ** 9 + 7)
print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

for i in range(2, n+1):
    if i in p:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % s

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

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
#for i in range(m):
#a[i] = int(input())
a = [int(input()) for i in range(m)]
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

for j in range(2,n+1):
  if j in a:
    dp[j] = 0
  else:
    dp[j] = dp[j-1]+dp[j-2]
print(dp[n]%1000000007)



### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
#for i in range(m):
 # a[i] = int(input())
a = set([int(input()) for i in range(m)])
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

for j in range(2,n+1):
  dp[j] = (dp[j-1]+dp[j-2])%1000000007
  if j in a:
    dp[j] = 0
print(dp[n])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 2)
        self.pow = [1] * (self.length + 2)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod
        self.pow[self.length+1] = self.pow[self.length] * self.base % self.mod 

    def get(self, l, r):
        t = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.mod
        return t
    
    def get_wsuff(self, l, r, suff):
        hash_suff = (self.hash[r] + ord(suff)) * self.base % self.mod
        t = (hash_suff - self.hash[l] * self.pow[r+1-l]) % self.mod
        return t

ss = []
n = int(input())
for _ in range(n):
    ss.append(input().rstrip())
ss.sort(key=lambda x: len(x), reverse=True)

words = dict()
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len)
    if rh in words:
        ans += words[rh]
    initial = set()
    for i, ch in enumerate(s):
        initial.add(ch)
        for key in initial:
            rh = RH.get_wsuff(0, word_len-i-1, key)
            if rh in words:
                words[rh] += 1
            else:
                words[rh] = 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import defaultdict

def empty_list():
    return [0] * 26

class RollingHash():
    def __init__(self, s):
        length = len(s)
        base = 1009
        # self.mod = (1 << 61) - 1
        self.mod = 67280421310721
        self.hash = [0] * (length + 2)
        self.pow = [1] * (length + 2)

        for i in range(length):
            self.hash[i+1] = (self.hash[i] + s[i]) * base % self.mod
            self.pow[i+1] = self.pow[i] * base % self.mod
        self.pow[length+1] = self.pow[length] * base % self.mod 

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        return t % self.mod

ss = []
n = int(input())
for _ in range(n):
    ss.append([ord(item) for item in input().rstrip()])
ss.sort(key=lambda x: len(x), reverse=True)

orda = ord("a")
words = defaultdict(empty_list)
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len-1)
    ans += words[rh][s_rev[-1] - orda]
    initial = [0] * 26 
    for i, ch in enumerate(s):
        initial[ch - orda] = 1
        for j, is_initial in enumerate(initial):
            if is_initial:
                rh = RH.get(0, word_len-i-1)
                words[rh][j] += 1
print(ans)