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

#137c
N = int(input())
sList = []
ans = 0

#文字を読み込みつつ、出現回数を辞書化して、配列に追加
for i in range(N): #2<N<10^5
    # https://www.lifewithpython.com/2015/05/python-count-characters-in-string.html
    string = str(input())

    #辞書化
    #counter = {}
    #for c in string:
    #    if not c in counter:
    #        counter[c] = 1
    #    else:
    #        counter[c] += 1
    #sList.append(counter)
    #↓リスト内包表記なら1行で書ける
    dictionarized_string = {letter: string.count(letter) for letter in string}
    ans += sList.count(dictionarized_string)
    sList.append(dictionarized_string)
    
#全通りを比較
#for i in range(N-1):
#    for j in range(i+1,N,1):
#        if sList[i]==sList[j]:
#            ans = ans+1
#↑.countで1行で済んだ  

print(ans)

### FIXED CODE ###

#137c
N = int(input())
s_dict = {}
ans = 0

#文字を読み込みつつ、出現回数を辞書化して、辞書に追加
for i in range(N): #2<N<10^5
  # https://www.lifewithpython.com/2015/05/python-count-characters-in-string.html
  string = list(input())
  string.sort(reverse=False)
  
  #print(tuple(string))
    
  if tuple(string) in s_dict:
    s_dict[tuple(string)] += 1
  else:
    s_dict[tuple(string)] = 1

for i in s_dict.values():
  if i != 1:
    ans += sum([i for i in range(1,i)])

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

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()))
ab = list()
for a in A:
    for b in B:
        ab.append(a+b)
ab.sort(reverse=True)
C.sort(reverse=True)
abc = []
for a in ab[:k]:
    for b in C:
        abc.append(a+b)
abc.sort(reverse=True)
print(*abc[:k], sep="\n")

### FIXED CODE ###

import heapq as hq
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()))
ab = []
for a in A:
    for b in B:
        hq.heappush(ab, -a-b)
abc = []
cnt = 0
while cnt < k and ab:
    cnt += 1
    a = hq.heappop(ab)
    for b in C:
        hq.heappush(abc, a-b)
cnt = 0
while cnt < k:
    print(-hq.heappop(abc))
    cnt += 1
### BUGGY CODE ###

def main():
    H,W,M = map(int,input().split())
    list = []
    dict_H = {key:0 for key in range(1,H+1,1)}
    dict_W = {key:0 for key in range(1,W+1,1)}
    for i in range(M):
        h,w = map(int,input().split())
        dict_H[h] += 1
        dict_W[w] += 1
        list.append((h,w))
    #print(list)
    maxH = max(dict_H.values())
    maxW = max(dict_W.values())
    wi = [i for i in range(1,W+1,1) if dict_W[i] == maxW]
    #print(retuH,gyoW,wi)
    for h in [i for i in range(1,H+1,1) if dict_H[i] == maxH]:
        for w in wi:
            if ((h,w) not in list):
                return maxH + maxW
    return maxH + maxW -1

print(main())


### FIXED CODE ###

def main():
    H,W,M = map(int,input().split())
    dict_gyo = {key: 0 for key in range(H)}
    dict_retu = {key: 0 for key in range(W)}
    dict_ichi = {}
    for i in range(M):
        h,w = map(int,input().split())
        dict_gyo[h-1] += 1
        dict_retu[w-1] += 1
        dict_ichi[(h-1,w-1)] = 1

    #print(dict_gyo,dict_ichi)

    maxgyo = max(dict_gyo.values())
    maxretu = max(dict_retu.values())
    #maxgyo_k = max(dict_gyo, key = dict_gyo.get)
    #maxretu_k = max(dict_retu, key = dict_gyo.get)
    #print(maxgyo_k,maxretu_k)
    result = maxgyo + maxretu - 1
    wi = [i for i in range(W) if dict_retu[i] == maxretu]
    for h in [i for i in range(H) if dict_gyo[i] == maxgyo]:
        for w in wi:
            if (h,w) not in dict_ichi:
                result = maxgyo + maxretu
                return result

    return result




print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    answer = answer * (math.factorial(n+r-1)//math.factorial(n-1)//math.factorial(r)) % (10**9+7)

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

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
        if i * i > a:
            fa.append([a,1])
            break

    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    a = 1
    for j in range(n,n+r):
        a = a * j
    for j in range(r):
        a = a // (j+1)
    answer = answer * a % (10**9+7)

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

N = int(input())

if N%2 == 0:
  print(N, N, N//2)
else:
  for h in range(3500, -1, -1):
    num = N*h*3501; diff_num = N*h
    dem = 4*h*3501 - N*(h+3501); diff_dem = 4*h - N
    for n in range(3500, -1, -1):
      num -= diff_num
      dem -= diff_dem
      if dem <= 0:
        break
      if num%dem == 0:
        print(h, n, num//dem)
        quit()

### FIXED CODE ###

N = int(input())

if N%2 == 0:
  print(N, N, N//2)
else:
  for h in range(1, 3501):
    for n in range(1, 3501):
      num = N*h*n
      dem = 4*h*n - N*(h+n)
      if dem > 0 and num%dem == 0:
        print(h, n, num//dem)
        quit()
### BUGGY CODE ###

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

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    for j in range(len(s)):
        if(s[j:j+2] == 'AC'):
            count += 1
    print(count)



### FIXED CODE ###

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

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    while(s.find('A') != -1):
        j = s.find('A')
        if(s[j:j+2] == 'AC'):
            count+=1
            s = s[j+2:]
        else:
            s = s[j+1:]
    print(count)
"""
#愚直なやり方だとTLEになってしまう。
#累積和とよばれるテクニックを使う
#https://qiita.com/drken/items/56a6b68edef8fc605821#問題-3-atcoder-abc-122-c---get-ac

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

#区間配列
a = [0] * len(S)
#累積和配列
s = [0] * (len(S) +1)

#左がAである文字Cは何番目にあるか求める
for i in range(len(S)):
    if S[i] == 'C':
        if S[i-1] == 'A':
            a[i] = 1 #i番目に'AC'のCがある (添字が0から始まるため実際にはi-1番目 i番目は'A')

#累積和を計算する
for i in range(1,len(a)+1):
    s[i] = s[i-1] + a[i-1]

#区間内にその文字があるか求める

for i in range(Q):
    lq,rq = map(int,input().split())
    print(s[rq] - s[lq])
### BUGGY CODE ###

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

a.sort()
p = []
k = set()
while a:
    prime = min( a )

    p.append( prime )

    i = 0
    flag = 0
    while i < len( a ):
        if a[ i ] == prime and flag == 1:
            k.add( prime )
        flag = 1
        if a[ i ] % prime == 0:
            a.pop( i )
            continue
        i += 1

# print( p, k )
print( len( p ) - len( k ) )

### FIXED CODE ###

# 以下カンニング
n = int( input() )
a = list( map( int, input().split() ) )

max_a = max( a )

c = {} # c[ a_i ] = aに含まれるa_iの個数
d = {} # d[ a_i ] = aにa_iの約数( < a_i )があるか(bool)
for a_i in a:
    try:
        c[ a_i ] += 1
    except KeyError:
        c[ a_i ] = 1
        d[ a_i ] = False # 初期値

for a_i in a:
    if c[ a_i ] > 0:
        tmp = 2 * a_i
        while tmp <= max_a:
            d[ tmp ] = True
            tmp += a_i

ans = 0
for a_i in a:
    if c[ a_i ] == 1 and d[ a_i ] == False:
        ans += 1

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

from collections import Counter

N = int(input())
S = [input() for i in range(N)]
S.sort(reverse=False)
clist = Counter(S)
tmp = 0
rlist = []

for i in range(len(clist)):
	if tmp <= int(clist.most_common()[i][1]):
		tmp = int(clist.most_common()[i][1])
		rlist.append(clist.most_common()[i][0])

rlist.sort(reverse=False)

for i in range(len(rlist)):
  print(rlist[i])

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for _ in range(N)]
clist = Counter(S)
M = max(clist.values())
rlist = []

for i in clist.keys():
    if clist[i] == M:
        rlist.append(i)

rlist.sort(reverse=False)

for i in range(len(rlist)):
  print(rlist[i])
### BUGGY CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, K = getNM()
red = N - K

def cmb(x, y):
    r = 1
    for i in range(1, y + 1):
        r = (r * (x - i + 1) * pow(i, mod - 2, mod)) % mod
    return r

for i in range(1, K + 1):
    ans = (cmb(red + 1, i) * cmb(K - 1, i - 1)) % mod
    print(ans)

### FIXED CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, K = getNM()
red = N - K

def cmb(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b

for i in range(1, K + 1):
    ans = (cmb(red + 1, i) * cmb(K - 1, i - 1)) % mod
    print(ans)
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if not n+1>i+j+k>0:continue
      dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    n = s - x
    ok = Q
    ng = -1
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if D[mid] >= n:
        ok = mid
      else:
        ng = mid
    l = ok

    n = t - x
    ok = Q
    ng = l - 1
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if D[mid] >= n:
        ok = mid
      else:
        ng = mid
    r = ok

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()


### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
### BUGGY CODE ###

N, M = map(int, input().split())
S = 1
p = 0
for i in range(2, int(M ** (1/2)) + 1):
  if M % i == 0:
    p = 1
if p != 0:
  for i in range(1, M // N + 1):
    if M % i == 0:
      S = i
print(S)

### FIXED CODE ###

N, M = map(int, input().split())
S = 1
p = 0
X = []
for i in range(2, int(M ** (1/2)) + 1):
  if M % i == 0:
    if i <= M // N:
      p = i
      X.append(i)
    else:
      break
if M // N <= int(M ** (1/2)):
  if p != 0:
    S = p
else:
  if p != 0:
    S = M
    q = 0
    while S > M // N:
      S = M // X[q]
      if S <= M // N:
        break
      q += 1
      if q == len(X):
        break
    if q == len(X):
      S = max(X)
print(S)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = []
    C = [0] * N

    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        # divisors.sort()
        return divisors

    for i in range(N):
        if A[N - i - 1] == 1:
            if C[N - i - 1] == 0:
                B.append(N - i)
                D = make_divisors(N - i)
                for d in D:
                    C[d - 1] += 1
                    C[d - 1] %= 2
        else:
            if C[N - i - 1] == 1:
                B.append(N - i)
                D = make_divisors(N - i)
                for d in D:
                    C[d - 1] += 1
                    C[d - 1] %= 2
    print(len(B))
    print(*B, sep=" ")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = []
    C = [0] * N

    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        # divisors.sort()
        return divisors

    for i in range(N):
        if A[N - i - 1] == 1:
            if C[N - i - 1] == 0:
                B.append(N - i)
                D = make_divisors(N - i)
                for d in D:
                    C[d - 1] += 1
                    C[d - 1] %= 2
        else:
            if C[N - i - 1] == 1:
                B.append(N - i)
                D = make_divisors(N - i)
                for d in D:
                    C[d - 1] += 1
                    C[d - 1] %= 2
    print(len(B))
    print(*B, sep=" ")


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

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
a  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ans = a[0]
for a_ in a[1:]:
    ans *= a_
print(-1 if ans > 10 ** 18 else ans)


### FIXED CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
a  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

if 0 in a:
    print(0)
    exit()

ans = a[0]
for a_ in a[1:]:
    if ans * a_ <= 10 ** 18:
        ans *= a_
    else:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(['#'] + list(input()) + ['#'])
grid.append(['#'] * (w+2))

l = [[0] * (w+2) for _ in range(h+2)]
r = [[0] * (w+2) for _ in range(h+2)]
u = [[0] * (w+2) for _ in range(h+2)]
d = [[0] * (w+2) for _ in range(h+2)]

#for i in range(h+2):
#    print(grid[i])

for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == '#':
            continue
        else:
            l[i][j] = l[i][j-1]+1

for i in range(1,h+1):
    for j in range(w+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            r[i][j] = r[i][j+1]+1

for j in range(1,w+1):
    for i in range(1,h+1):
        if grid[i][j] == '#':
            continue
        else:
            u[i][j] = u[i-1][j]+1

for j in range(1,w+1):
    for i in range(h+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            d[i][j] = d[i+1][j]+1

ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)

print(ans)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

def isOK(score):
    min_cost = sum_a - sum([min(A,score // F) for A,F in zip(a,f)])
    if min_cost <= k:
        return True
    else:
        return False


def binary_search():
    ok = 10 ** 12 + 100
    ng = -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok



n,k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
f = sorted(list(map(int, input().split())))

sum_a = sum(a)
ans = binary_search()
print(ans)

### FIXED CODE ###

def isOK(score):
    min_cost = sum_a - sum([min(A,score // F) for A,F in zip(a,f)])
    if min_cost <= k:
        return True
    else:
        return False


def binary_search():
    ok = 10 ** 12 + 100
    ng = -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok



n,k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
f = sorted(list(map(int, input().split())))

sum_a = sum(a)
ans = binary_search()
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a1 = int(input())
    a.append(a1)
countc = 0
while len(a) > 0:
    count = len(a) - 1
    count1 = 0
    k = 1
    while count - count1 > 0:
        if a[count-1-count1] >= a[count]:
            count1 = count1 + 1
            k = 0
        else:
            del a[count]
            count = count - 1 - count1
            k = 1
    del a[count]
    countc = countc + 1
print(countc)

### FIXED CODE ###

import bisect
n = int(input())
l = [0 for i in range(n)]
for i in range(n):
    a1 = int(input())
    l[n-1-i] = a1
h = [l[0]]
ans = 1
for i in range(1,n):
    a = bisect.bisect_right(h,l[i])
    if ans == a:
        ans += 1
        h.append(l[i])
    else:
        h[a] = l[i]
print(ans)
### BUGGY CODE ###

from fractions import *
N, M = map(int, input().split())

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

a = sorted(a)
bc = [list(map(int, input().split())) for i in range(M)]

bc = sorted(bc)    

subar = a
for i in bc:
    sc = [i[1]] * i[0]
    suba = []
    ra = subar[i[0]:]
    if i[0] == len(a):
        suba = a
    suba = subar[:i[0]]
    if i[1] - max(suba) < 0:
        continue
    subar = sc + ra
    subar.sort()

print(sum(subar))





### FIXED CODE ###

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

a.sort()

pairs = [list(map(int, input().split())) for _ in range(m)]
pairs = sorted(pairs, key=lambda x: x[1])
cnt = 0
ans = 0
while cnt < n:
    if pairs != [] and a[-1] < pairs[-1][1] and cnt+pairs[-1][0] <= n:
        cnt += pairs[-1][0]
        ans += pairs[-1][0]*pairs[-1][1]
        pairs.pop(-1)
    elif pairs != [] and a[-1] < pairs[-1][1] and cnt+pairs[-1][0] > n:
        ans += (n - cnt)*pairs[-1][1]
        cnt += n - cnt
        break
    else:
        cnt+= 1
        ans += a[-1]
        a.pop(-1)

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

def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop(0)
			D[cur] = dd
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()


### FIXED CODE ###

def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		if D[v - 1] >= d:
			continue
		D[v - 1] = d
		q = [v - 1]
		while q:
			cur = q.pop()
			dd = D[cur]
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd - 1:
					continue
				D[nxt] = dd - 1
				q.append(nxt)
	print("\n".join(map(str, C)))

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

#それぞれの桁を考えた時にその桁を一つ多めに払うのかちょうどで払うのかで場合分けする

import math
n=int(input())
k=math.floor(math.log10(n))+1#桁数
n=str(n)#それぞれの桁にアクセスするためにイテラブルにする

#それぞれの桁を見ていくが、そのままと一つ多い状態から引く場合と二つあることに注意
dp=[[-1,-1] for _ in range(k)]
for i in range(k):
    if i==0:
        dp[i][0]=min(1+(10-int(n[i])),int(n[i]))
        dp[i][1]=min(1+(10-int(n[i])-1),int(n[i])+1)
    else:
        dp[i][0]=min(dp[i-1][1]+(10-int(n[i])),dp[i-1][0]+int(n[i]))
        dp[i][1]=min(dp[i-1][1]+(10-int(n[i])-1),dp[i-1][0]+int(n[i])+1)

print(dp[k-1][0])

### FIXED CODE ###

#それぞれの桁を考えた時にその桁を一つ多めに払うのかちょうどで払うのかで場合分けする

n=[int(x) for x in list(input())]#それぞれの桁にアクセスするためにイテラブルにする
k=len(n)

#それぞれの桁を見ていくが、そのままと一つ多い状態から引く場合と二つあることに注意
dp=[[-1,-1] for _ in range(k)]
dp[0]=[min(1+(10-n[0]),n[0]),min(1+(10-n[0]-1),n[0]+1)]
for i in range(1,k):
    dp[i]=[min(dp[i-1][1]+(10-n[i]),dp[i-1][0]+n[i]),min(dp[i-1][1]+(10-n[i]-1),dp[i-1][0]+n[i]+1)]
print(dp[k-1][0])