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

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
        d[b].append((a,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
import math
n = int(input())
a = list(map(int,input().split()))
for i in range(len(a)):
  o = 0
  b = a[:]
  del b[i]
  c = collections.Counter(b)
  for i in c.values():
    if i-2<1:
      r=1
    else:
      r=i-2
    o += (math.factorial(i) // math.factorial(r)//2)
  print(int(o))
  


### FIXED CODE ###

from collections import Counter
def comb(x):
    return x*(x-1)//2
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
b = 0
for i in c.values():
    b+=comb(i)
for k in range(n):
    print(b-c[a[k]]+1)
### BUGGY CODE ###

# coding: utf-8

n,a,b=map(int,input().split())
cnt=0

x=n//(a+b)*a       # (a+b)個までで入っている青の数（入力例1の場合，3個）
y=n%(a+b)       # nを(a+b)で割った余り（入力例1の場合，1個）

for i in range(y):
    x += 1
    cnt += 1
    
    if cnt == a:
        break

print(x)

### FIXED CODE ###

# coding: utf-8

n,a,b=map(int,input().split())
cnt=0

x=n//(a+b)*a       # a+b個までで入っている青の数（入力例1の場合，3個）
y=n%(a+b)       # nを(a+b)で割った余り（入力例1の場合，1）

if y>a:
    x = x + a
else:
    x = x + y

print(x)
### BUGGY CODE ###

from collections import Counter

N = int(input())
src = list(map(int,input().split()))
sor = Counter(src)

for n in range(N):
  i = src[n]
  count = 0
  for key,value in sor.items():
    if int(key) == i:
      count += (value-1)*(value-2)/2
    else:
      count += value*(value-1)/2
  print(int(count))

### FIXED CODE ###

N = int(input())
src = list(map(int,input().split()))
dic = {}
for n in range(N):
  if dic.get(src[n]) == None:
    dic[src[n]] = 1
  else:
    dic[src[n]] += 1
a = 0
for key, value in dic.items():
  a += value*(value-1)//2
ans = []
for s in src:
  ans.append(a - dic[s]*(dic[s]-1)//2 + (dic[s]-1)*(dic[s]-2)//2)
for b in ans:
  print(b)
### BUGGY CODE ###

n = int(input())

input_patterns = []

patterns = {}

a_max = ord('z')
a_min = ord('a')


def init_key():
    ini_key = []
    for i in range(26):
        ini_key.append(0)
    return ini_key

for i in range(n):
    val = input()
    input_patterns.append(val)

#input_patterns = ['acornistnt', 'peanutbomb', 'constraint']
    
for inp in input_patterns:
    key = init_key()
    for j in range(len(inp)):
        # make [0, 0, 1, 0, 2, 3, ...]
        #       a  b  c  d  e  f  
        for k in range(26):
            if inp[j] == chr(ord('a') + k):
                key[k] = key[k] + 1

    skey = ''
    for k in range(26):
        skey = skey + str(key[k])

    if skey in patterns:
        patterns[skey] = patterns[skey] + 1
    else:
        patterns[skey] = 1

result = 0

for skey in patterns:
    if patterns[skey] > 1:
        for i in range(1, int(patterns[skey])):
            result = result + i

print('{}'.format(result))


### FIXED CODE ###

n = int(input())

input_patterns = []

patterns = {}

def init_key():
    ini_key = []
    for i in range(26):
        ini_key.append(0)
    return ini_key

for i in range(n):
    val = input()
    input_patterns.append(val)

count = 0
for inp in input_patterns:
    key = sorted(inp)
    skey = ''

    for k in range(len(key)):
        skey = skey + key[k]

    if skey in patterns:
        patterns[skey] = patterns[skey] + 1
    else:
        patterns[skey] = 1

    if patterns[skey] > 1:
        count = count + patterns[skey] - 1
    
print('{}'.format(count))
### BUGGY CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

Gs = np.asarray(S)
Gs_ = np.rot90(Gs, k=1)

def count_light(Gs):
    Gc = []
    for gs in Gs:
        count = 0
        gc = []
        for s in gs:
            if s == '#':
                count = 0
                gc.append(0)
            else:
                count += 1
                gc.append(count)
        Gc.append(gc)

    Gc = np.asarray(Gc)

    Gn = []
    for gc in Gc:
        count = -1
        gn = []
        for c in gc[::-1]:
            if c == 0:
                count = -1
                gn.append(0)
            else:
                if count == -1:
                    count = c
                gn.append(count)
        Gn.append(gn[::-1])

    Gn = np.asarray(Gn)
    return Gn

Gn = count_light(Gs)
Gn_ = count_light(Gs_)
Gn_ = np.rot90(Gn_, k=3)

Gsum = Gn+Gn_
ans = np.max(Gsum)-1

        
print(ans)

### FIXED CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)
### BUGGY CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

MOD = 998244353
n,m,k = MI()

s = [1]
for i in range(2, n):
    s.append(s[-1]*i%MOD)
if m == 1 and k < n-1:
    print(0)
    exit(0)
elif m == 1 and k == n-1:
    print(1)
    exit(0)
ans = m*pow(m-1, n-1, MOD)%MOD
for i in range(1, k+1):
    tmp = m*pow(m-1, n-1-i, MOD)*s[n-2]*pow(s[n-2-i], MOD-2, MOD)*pow(s[i-1], MOD-2, MOD)
    ans += tmp
    ans %= MOD
print(ans)


### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

MOD = 998244353
n,m,k = MI()

s = [1]
for i in range(2, n):
    s.append(s[-1]*i%MOD)
if m == 1 and k < n-1:
    print(0)
    exit(0)
elif m == 1 and k == n-1:
    print(1)
    exit(0)
elif k == n-1:
    print(pow(m, n, MOD))
    exit(0)
ans = m*pow(m-1, n-1, MOD)%MOD
for i in range(1, k+1):
    tmp = m*pow(m-1, n-1-i, MOD)*s[n-2]*pow(s[n-2-i], MOD-2, MOD)*pow(s[i-1], MOD-2, MOD)
    ans += tmp
    ans %= MOD
print(ans)
### BUGGY CODE ###

n=int(input())
sum=0
a=list(map(int, input().split()))
for i in range(n):
  for j in range(i+1, n):
    #print(i,j)
    sum+=a[i]*a[j]
    sum = sum%((10**9)+7)

print(sum)


### FIXED CODE ###

n=int(input())
sums=0
a=list(map(int, input().split()))
b = sum(a)
for i in range(n):
  b -= a[i]
  sums += a[i]*b
  sums = sums%((10**9)+7)
print(sums)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp =[0,1] + [0] * n
m = 10**9+7
for i in range(2,n+2):
    if i-1 not in a:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= m
print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp =[0,1] + [0] * n
m = 10**9+7
for i in a:
    dp[i+1] = -1
for i in range(2,n+2):
    if dp[i] == 0:
        dp[i] = max(0,dp[i-1]) + max(0,dp[i-2])
        dp[i] %= m
    if dp[i-1] == 0 and dp[i-2] == 0:
        print(0)
        exit()
print(dp[-1])
### BUGGY CODE ###

from scipy.misc import comb
N,*A = map(int,open(0).read().split())
d = {}
for i in A:
    d[i]= d[i]+1 if i in d else 1
for i in A:
    dd = d.copy()
    dd[i] -= 1
    sum = 0
    for k,v in dd.items():
        sum += comb(v,2,exact=True)
    print(sum)

### FIXED CODE ###

from scipy.misc import comb
N,*A = map(int,open(0).read().split())
d = {}
for i in A:
    d[i]= d[i]+1 if i in d else 1
count_d = {}
sum = 0
for k,v in d.items():
    count_d[k] = comb(v,2,exact=True)
    sum += count_d[k] 
 
for i in A:
    if count_d[i]>=1:
        print(sum - (d[i]-1))
    else:
        print(sum)
### BUGGY CODE ###

import numpy as np
from collections import deque
n=int(input())
edge=np.array(list(list(map(int,input().split())) for _ in range(n-1)))
color=np.zeros(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=[]
  seen=[]
  for i in range(n-1):
    if s in edge[i]:
      e=edge[i][edge[i]!=s]
      if color[i]==0:
        d.append(e[0])
        check.append(i)
      else:
        seen.append(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))        
    

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
k=0
used=[-1]*n
seen=[-1]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
    k=max(k,len(node[pair[0]]),len(node[pair[1]]))
print(k)
ans={}
d=deque()
d.append(0)
while d:
    i=d.pop()
    seen[i]=1
    res=1
    for j in node[i]:
        if seen[j]==1:
            continue
        d.appendleft(j)
        if res!=used[i]:
            ans[(i,j)]=res
        else:
            res+=1
            ans[(i,j)]=res
        used[j]=res
        res+=1
for pair in v:
    a,b=pair
    if (a,b) in ans:
        print(ans[(a,b)])
    else:
        print(ans[(b,a)])
### BUGGY CODE ###

n = int(input())
x = input()
xlis = []
for i in range(n):
    xlis.append(x[i])
xi = []
def flip(m):
    if m == "1":
        return "0"
    else:
        return "1"
for i in range(n):
    if i == 0:
        xlis[i] = flip(xlis[i])
        xi.append("".join(xlis))
    else:
        xlis[i-1] = flip(xlis[i-1])
        xlis[i] = flip(xlis[i])
        xi.append("".join(xlis))
def popcount(m):
    return bin(m).count("1")
for i in range(len(xi)):
    xi[i] = int(xi[i], 2)
for i in range(len(xi)):
    m = xi[i]
    ans = 0
    while m != 0:
        m %= popcount(m)
        ans += 1
    print(ans)

### FIXED CODE ###

n = int(input())
x = int(input(),2)

def popcount(l):
    return bin(l).count("1")
def count(l):
    res = 0
    while l != 0:
        p = popcount(l)
        l %= p
        res += 1
    return res
m = popcount(x)
x_plus = x%(m+1)
if m != 1:
    x_minus = x%(m-1)
else:
    x_minus = 1
lis_plus = [0]*n
lis_minus = [0]*n
for i in range(n):
    if i == 0:
        lis_plus[i] = 1%(m+1)
        if m != 1:
            lis_minus[i] = 1%(m-1)
    else:
        lis_plus[i] = lis_plus[i-1]*2%(m+1)
        if m != 1:
            lis_minus[i] = lis_minus[i-1]*2%(m-1)
for i in range(n):
    if (x >> (n-i-1)) & 1:
        if m == 1:
            print(0)
        else:
            print(count((x_minus - lis_minus[-i-1])%(m-1)) + 1)
    else:
        print(count((x_plus + lis_plus[-i-1])%(m+1)) + 1)
### BUGGY CODE ###

import math
N=int(input())
a=0
b=0
x=0
for i in range(N+1):
  a=math.sqrt(i)
  b=int(a)
  if(i==b*b):
   x=i
print(x)

### FIXED CODE ###

import math
N=int(input())
n=math.sqrt(N)
m=math.floor(n)
print(m*m)
### BUGGY CODE ###

import collections

N=int(input())
A=[int(_) for _ in input().split(" ")]
Q=int(input())

c = collections.Counter(A)


#d['k10'] = d.pop('k1')    
    
for i in range(Q):
  B,C=map(int,input().split(" "))
  
  if C in c:
    c[C] += c[B]
    del c[B]
  else:
    c[C] = c[B]
    del c[B]
  
  #print(c)
  
  s=list(c.keys())
  j=0
  ans=0
  for v in c.values():
    ans += s[j]*v
    j=j+1
  
  print(ans)


  
  

### FIXED CODE ###

import collections

N=int(input())
A=[int(_) for _ in input().split(" ")]
Q=int(input())

c = collections.Counter(A)

ans=0
for v in c:
  ans += v*c[v]

#print(c)
#d['k10'] = d.pop('k1')    
    
for i in range(Q):
  B,C=map(int,input().split(" "))
  
  if C in c:
    ans=ans-B*c[B]+C*c[B]
    c[C] += c[B]
    del c[B]
  else:
    ans=ans-B*c[B]+C*c[B]
    c[C] = c[B]
    del c[B]
  
  print(ans)
### BUGGY CODE ###

n=int(input())
l=[*map(int,input().split())]
a=1000
c=0
for i in range(n-1):
  if l[i]>l[i+1]:
    a+=c*l[i]
    c=0
  if l[i]<l[i+1]:
    while a>=l[i]:
      a-=l[i]
      c+=1
print(a+c*l[n-1])

### FIXED CODE ###

n=int(input())
l=[*map(int,input().split())]
a=1000
c=0
for i in range(n-1):
  if l[i]>l[i+1]:
    a+=c*l[i]
    c=0
  if l[i]<l[i+1]:
    while a>=l[i]:
      t=a//l[i]
      a-=t*l[i]
      c+=t
print(a+c*l[n-1])
### BUGGY CODE ###

H, W, N = map(int,input().split())              
paints = []                                     
for i in range(N):
    paints.append(tuple(map(int,input().split())))
D = [(0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1)]
black_square = [0 for i in range(10)]

for i in range(2,H):
    for j in range(2,W):
        count = 0
        if (i,j) in paints: count += 1
        for k in range(8):
            if (i + D[k][0], j + D[k][1]) in paints: count += 1
        black_square[count] += 1

for b in black_square:
    print(b)

### FIXED CODE ###

from collections import Counter
import itertools

H, W, N = map(int,input().split())
blacks = []
for i in range(N):
    blacks.append(tuple(map(int,input().split())))

blacks_in_square = [(x+dx,y+dy) for x,y in blacks\
                    for dx in [-1,0,1] for dy in [-1,0,1]\
                    if 1 < x+dx < H and 1 < y+dy < W]

ans = [0] * 10
for x,y in Counter(Counter(blacks_in_square).values()).items():
    ans[x] = y
ans[0] = (H-2) * (W-2) - sum(ans)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

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

ans=0
for k in range(n-1):
    for j in range(k+1,n):
        ans+=(i[k]*i[j])%(10**9+7)

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


### FIXED CODE ###

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

m=sum(i)

ans=0
for k in range(n):
    ans+=(i[k]*(m-i[k]))
ans=ans//2
ans=ans%(10**9+7)
print(ans)
### BUGGY CODE ###

data_map = [0]*4001

for i1 in range(1001):
  for i2 in range(1001):
    for i3 in range(1001):
      for i4 in range(1001):
        data_map[i1+i2+i3+i4] += 1

while True:
  try:
    line = int(raw_input())
  except:
    break
  print data_map[line][3]

### FIXED CODE ###

data_map = [[0] + [1]*1001 + [0]*3000, [0]*4002, [0]*4002, [0]*4002]
for i in range(1,4):
  for j in range(1,4002):
    k = 0 if j < 1000 else j-1000
    data_map[i][j] = sum(data_map[i-1][k:j+1])

while True:
  try:
    line = int(raw_input())
  except:
    break
  print data_map[3][line+1]
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())

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

for _ in range(m):
    l, r = map(int, input().split())
    for i in range(l - 1, r):
        pass_id[i] += 1

# print(pass_id)
print(pass_id.count(m))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())

head = 1
tail = n

for _ in range(m):
    l, r = map(int, input().split())
    head = max(head, l)
    tail = min(tail, r)

if head > tail:
    print(0)
else:
    print(tail - head + 1)
### BUGGY CODE ###

from collections import defaultdict
q = int(input())
for _ in range(q):
    x = input()
    y = input()
    len_x = len(x)
    len_y = len(y)
    if len_x < len_y:
        len_x, len_y = len_y, len_x
        x, y = y, x
    set_x = set(x)
    c = defaultdict(list)
    for i, s in enumerate(x):
        c[s].append(i)
    li = [0] * len_x
    for s in y:
        if s in set_x:
            for i in c[s][::-1]:
                if i == 0:
                    li[i] = 1
                else:
                    li[i] = max(li[:i]) + 1
    print(max(li))



### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

#import time as time

lines =  input().split()
n = int(lines[0])
m = int(lines[1])
#n,m = map(int,input().split())

py = []
od = [[]*1 for i in range(n)]

#print ("create list: " + str(time.time() - s) )
#s = time.time()
for i in range(0,m):

    lines =  input().split()
    p = int(lines[0])
    y = int(lines[1])
    py.append([p,y])
       
    odlen = len(od[p-1])
    od[p-1].append(y)
    od[p-1].sort()
    """ if odlen >= 1 :

        low = 0
        high = odlen - 1
        mid = odlen >> 1

        while low <= high:
            mid = (low + high) >> 1
            guess = od[p-1][mid]
            if guess == y:
                break
            if guess > y :
                high = mid - 1
            else:
                low  = mid + 1
        od[p-1].insert(low,y)

    else:
        od[p-1].append(y) """

#print ("sort: " + str(time.time() - s) )
#exit(0)

#s = time.time()
for i in range(0,m):
    py0 = py[i][0] 
    r = od[py0-1].index(py[i][1])

    tmp = py0
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = tmp // 10
    
    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(py0,end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(r+1)

#print ("index: " + str(time.time() - s) )

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
res = 0
m = 10**9 + 7
for i in range(0, len(li)-1):
    for j in range(i+1, len(li)):
            res += ((li[i]%m)*(li[j]%m))
print(res%m)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
res = 0
sum1 = sum(li)
sum2 = 0
m = 10**9 + 7
for i in range(0, len(li)-1):
    sum2 += li[i]
    res = (res + li[i]*(sum1-sum2))%m
print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def lcs(x, y):
    dp = {(0, 0): 0}
    for i in range(1, len(x) + 1):
        dp[(i, 0)] = 0
    for j in range(1, len(y) + 1):
        dp[(0, j)] = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)] + 1
            else:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j - 1)])

    return dp[(len(x), len(y))]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))


### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    S = [input() for _ in range(n)]
    word = sorted(list(set(S)))
    word_cnt = [0]*len(word)
    maxi = 0
    for i, w in enumerate(word):
        word_cnt[i] = S.count(w)
        maxi = max(maxi, word_cnt[i])
    for i, w in enumerate(word):
        if word_cnt[i] == maxi:
            print(w)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    S = [input() for _ in range(n)]
    word = collections.Counter(S).most_common()
    maxi = word[0][1]
    ans = []
    for w in word:
        if w[1] == maxi:
            ans.append(w[0])
        else:
            break
    ans.sort()
    a = "\n".join(ans)
    print(a)

if __name__ == '__main__':
    main()