Harryxun/stf_run huggingface dataset:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import sys,resource
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(ls,k):
    global ans
    #ddprint(f"dfs {k=} {ls=} - - - -")
    ll = [[] for i in range(26)]
    x = [0]*26
    for z in ls:
        c = ord(z[0][-1])-orda
        if len(z[0])==1:
            x[c] += 1
        else:
            ll[c].append((z[0][:-1],z[1]))
    #ddprint(f"{x=} {ll=}")
    for c in range(26):
        for z in ls:
            #if len(ls)==2:
            #    ddprint(f" z1 {z[1]} {k=} {c=} fst {first[z[1]][c]}")
            if first[z[1]][c]>=k and len(z[0])>1:
                ans += x[c]
                #if x[c]>0:
                #    ddprint(f"ans += {x[c]}")
    for c in range(26):
        if len(ll[c])>0:
            dfs(ll[c],k+1)

setrlim()
n = inn()
ls = []
first = [[-1]*26 for i in range(n)]
orda = ord('a')
for i in range(n):
    s = ins()
    ls.append((s,i))
    for c in range(26):
        p = s.find(chr(orda+c))
        first[i][c] = (len(s)-1-p) if p>=0 else -1
#ddprint(f"{ls=}")
#ddprint(f"{first=}")
ans = 0
dfs(ls,0)
print(ans)


### FIXED CODE ###

inn = lambda : int(input())
ins = lambda : input().strip()
DBG = True # and False

def ddprint(x):
  if DBG:
    print(x)

import sys,resource
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(l,k):
    global ans
    #ddprint(f"dfs {k=} {l=} - - - -")
    ll = [[] for i in range(26)]
    x = [0]*26
    for z in l:
        #ddprint(f"lsz {ls[z]} {z=} {k=}")
        c = ord(ls[z][-k-1])-orda
        if len(ls[z])==k+1:
            x[c] += 1
        else:
            ll[c].append(z)
    #ddprint(f"{x=} {ll=}")
    for c in range(26):
        for z in l:
            #if len(ls)==2:
            #    ddprint(f" z1 {z[1]} {k=} {c=} fst {first[z[1]][c]}")
            if first[z][c]>=k and len(ls[z])>k+1:
                ans += x[c]
                #if x[c]>0:
                #    ddprint(f"ans += {x[c]}")
    for c in range(26):
        if len(ll[c])>1:
            dfs(ll[c],k+1)

setrlim()
n = inn()
ls = []
first = [[-1]*26 for i in range(n)]
orda = ord('a')
for i in range(n):
    s = ins()
    ls.append(s)
    for c in range(26):
        p = s.find(chr(orda+c))
        first[i][c] = (len(s)-1-p) if p>=0 else -1
#ddprint(f"{ls=}")
#ddprint(f"{first=}")
ans = 0
dfs(list(range(n)),0)
print(ans)
a,b=map(input().split())
if a>=13:
  print(b)
elif 12<=a<=6:
  print(b//2)
else:
  print(0)

### FIXED CODE ###

a,b=map(int,input().split())
if a>=13:
  print(b)
elif 6<=a<=12:
  print(b//2)
else:
  print(0)
α = int(input())
if str.isupper():
  print('A')
else:
  print('a')

### FIXED CODE ###

α = input()
if α.isupper():
  print('A')
else:
  print('a')
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
if n != 0 and a[0] >= 1:
    print(-1)
    exit()
val = 1
ans = 1
for i in range(n):
    ans += val * 2
    val *= 2
    val -= a[i+1]
    if val < 0:
        print(-1)
        exit()
    if val == 0 and i != (n-1):
        print(-1)
        exit()
    if i == n-2:
        val2 = val
val3 = (val2 - a[-2])
val -= val3
if val//2 > val2:
    print(-1)
    exit()
ans -= val//2
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
if n != 0 and a[0] >= 1:
    print(-1)
    exit()
if n == 0 and a[0] >= 2:
    print(-1)
    exit()
ar = list(reversed(a))
#print(ar)
com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])
#print(com)
com.reverse()
ans = 1
val = 1
for i in range(1,n+1):
    val *= 2
    ans += min(val,com[i])
    val -= a[i]
    if (i < n and val <= 0) or (i == n and val < 0):
        print(-1)
        exit()
print(ans)
A = int(input())
B = float(input())
print(int(A*B))

### FIXED CODE ###

a, b = input().split()
A = int(a)
B = float(b)
B100 = round(100*B)
 
C=A*B100
print(str(C//100))
N = int(input())
a = []
import fractions
for i in range(N):
    a.append(int(input()))
def lcd(m,n):
  c = fractions.gcd(m,n)
  return m*n/c
def ans(li):
  if len(li)=1:
    return li[0]
  else:
    li[0]=lcd(li[0],li[1])
    del li[1]
    return ans(li)
print(ans(a))


### FIXED CODE ###

N=int(input())#入力回数を決める
import fractions
from functools import reduce
li=[]
for i in range(N):
  li.append(int(input()))
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
print(lcm_list(li))
import numpy as np
from scipy.sparse.csgraph import floyd_warshall



n = int(input())
matrix = np.zeros((n, n),dtype=np.int64)
for i in range(n-1):
    a, b, c = map(int, input().split())
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
min_span_matrix = floyd_warshall(matrix, directed=False,
                                 return_predecessors=False)
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(int(min_span_matrix[x-1][k-1] + min_span_matrix[k-1][y-1]))


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)


n = int(input())
query = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))
q, k = map(int, input().split())
stack = deque([(k-1, 0, -1)])
dist = [0] * n
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx == per:
            continue
        if c != 0:
            stack.append((nx, cnt+c, now))
for i in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
import sys
import math


class Circle:
    def __init__(self, x, y, r):
        self.x = x
        self.y = y
        self.r = r

    def distance(self, other):
        dx = self.x - other.x
        dy = self.y - other.y
        return math.sqrt(dx ** 2 + dy ** 2)

    def intersection(self, other):
        d = self.distance(other)
        if self.r > d + other.r:
            return 2
        elif other.r > d + self.r:
            return -2
        elif d =< self.r + other.r:
            return 1
        else:
            return 0


#input_file = open(sys.argv[1], "r")

sys.stdin.readline()

for line in sys.stdin:
    (xa, ya, ra, xb, yb, rb) = tuple(map(float, line.split(' ')))
    ca = Circle(xa, ya, ra)
    cb = Circle(xb, yb, rb)
    print ca.intersection(cb)

### FIXED CODE ###


import sys
import math


class Circle:
    def __init__(self, x, y, r):
        self.x = x
        self.y = y
        self.r = r

    def distance(self, other):
        dx = self.x - other.x
        dy = self.y - other.y
        return math.sqrt(dx ** 2 + dy ** 2)

    def intersection(self, other):
        d = self.distance(other)
        if self.r > d + other.r:
            return 2
        elif other.r > d + self.r:
            return -2
        elif d <= self.r + other.r:
            return 1
        else:
            return 0


#input_file = open(sys.argv[1], "r")

sys.stdin.readline()

for line in sys.stdin:
    (xa, ya, ra, xb, yb, rb) = tuple(map(float, line.split(' ')))
    ca = Circle(xa, ya, ra)
    cb = Circle(xb, yb, rb)
    print ca.intersection(cb)
def main():
    N, K, S = map(int, input().split())
    MaxN = 10 ** 9
    if S == MaxN:
        A = [1] * N
    else:
        A = [MaxN] * N
    S = (S + 1) // 2
    if K != 0:
        for i in range(K + 1):
            if i % 2 == 0:
                A[i] = S
            else:
                A[i] = S - 1
    print(" ".join(map(str, A)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K, S = map(int, input().split())
    MaxN = 10 ** 9
    if S == MaxN:
        A = [S] * K + [1] * (N - K)
    else:
        A = [S] * K + [S + 1] * (N - K)

    print(" ".join(map(str, A)))


if __name__ == "__main__":
    main()
h, w, m = map(int, input().split())
mapa = [[0]*w for i in range(h)]
strings = [[0, i] for i in range(h)]
rows = [[0, i] for i in range(w)]
maxs = 0
maxr = 0
for i in range(m):
    h1, w1 = map(int, input().split())
    mapa[h1-1][w1-1] = 1
    strings[h1-1][0] += 1
    rows[w1-1][0] += 1
    if strings[h1-1][0] > maxs:
        maxs = strings[h1-1][0]
    if rows[w1-1][0] > maxr:
        maxr = rows[h1-1][0]
summa = maxs + maxr - 1
for i in range(h):
    if strings[i][0] == maxs:
        for j in range(w):
            if rows[j][0] == maxr:
                x = maxs + maxr
                if mapa[strings[i][1]][rows[j][1]] == 1:
                    x -= 1
                if x > summa:
                    summa = x
                    print(summa)
                    exit()
print(summa)


### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    max_s = max(strings)
    max_r = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == max_s:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == max_r:
            rows_max.append(i)
    
    forbidden_positions = set(mapa[strings_max[0]])
    for item in strings_max[1:]:
        forbidden_positions.intersection_update(set(mapa[item]))

    answer_set = set(rows_max).difference(forbidden_positions)
    if answer_set:
        print(max_s + max_r)
    else:
        print(max_s + max_r - 1)

main()
N,T = map(int,input().split())
A = list(map(int,input().split()))
LST = []

for a in A:
  LST.append((a,1))
  LST.append((a+T,-1))
  
LST.sort()

prev = -1
s = 0
ans = 0
for x,y in A:
  if y == 1:
    if s == 0:
      prev = x
    else:
      s += 1
  elif y == -1:
    s -= 1
    if s == 0:
      ans += (x - prev)
  
print(ans)



### FIXED CODE ###

N,T = map(int,input().split())
A = list(map(int,input().split()))
LST = []

for a in A:
  LST.append((a,1))
  LST.append((a+T,-1))
  
LST.sort()

prev = -1
s = 0
ans = 0
for x,y in LST:
  if y == 1:
    s += 1
    if s == 1:
      prev = x
  elif y == -1:
    s -= 1
    if s == 0:
      ans += (x - prev)
  
print(ans)
def main()
  a = input()
  b = input()

  if a/b == 0:
    print(a + b)
  else:
    print(b - a)

### FIXED CODE ###

A, B = map(int, input().split())
print(A+B if B % A == 0 else B-A)
from collections import Counter, defaultdict, deque
n = int(input())
#n,a,b = map(int,input().split())
# al = list(map(int,input().split()))

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

if n % 2 == 0:
    lst = [0]*n
    for i in range(1,n):
        x = (al[i-1]+n-1)/2
        y = x -al[i-1]
        #print(x,y)
        #print(n-x-1,x)
        lst[int(n-x-1)] += 1
        lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    #print(lst)
    if not 0 in lst:
        print(int(2**(n/2))%((10**9)+7))
    else:
        print(0)
else:
    lst = [0] * n
    for i in range(1, n):
        x = (al[i - 1] + n - 1) / 2
        y = x - al[i - 1]
        # print(x,y)
        #print(n - x - 1, x)
        lst[int(n - x - 1)] += 1
        lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    #print(lst)
    if not 0 in lst:
        print(int(2 ** ((n-1) / 2))%((10**9)+7))
    else:
        print(0)



### FIXED CODE ###

from collections import Counter

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

c_al = Counter(al)

if n % 2 == 0:
    for k,v in c_al.items():
        if v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))

elif n % 2 != 0:
    for k, v in c_al.items():
        if k == 0:
            if v != 1:
                print(0)
                exit()
        elif v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))
a,b,m = map(int,input().split())
ref = list(map(int,input().split()))
ran = list(map(int,input().split()))
ticket = []
ans = min(ref) + min(ran)
for i in range(m):
  t = list(map(int,input().split()))
  p = t[0] - 1
  q = t[1] - 1
  if ref[p] + ran[p] < ans:
    ans = ref[p] + ran[p]
print(ans)

### FIXED CODE ###

a,b,m = map(int,input().split())
ref = list(map(int,input().split()))
ran = list(map(int,input().split()))

ans = min(ref) + min(ran)

for i in range(m):
  t = list(map(int,input().split()))
  p = t[0] 
  q = t[1]
  c = t[2]
  if (len(ref) >= p and len(ran) >= q):
    if ref[p - 1] + ran[q - 1] - c < ans:
      ans = ref[p - 1] + ran[q - 1] - c
      
print(ans)
a = []
b = []
for i in range(3):
    ai = list(map(int, input().split()))
    a.append(ai)
n = int(input())
for i in range(n):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if a[j][k] == b:
                a[j][k] = 0

for i in range(3):
    if a[i][0] == 0 and a[i][1] == 0 and a[i][2] == 0:
        print("Yes")
        break
else:
    for i in range(3):
        if a[0][i] == 0 and a[1][i] == 0 and a[2][i] == 0:
            print("Yes")
            break
    else:
        if c[0][0] == 0 and c[1][1] == 0 and c[2][2] == 0:
            print("Yes")
        elif a[0][2] == 0 and a[1][1] == 0 and a[2][0] == 0:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

a = []
for i in range(3):
    ai = list(map(int, input().split()))
    a.append(ai)
n = int(input())
for i in range(n):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if a[j][k] == b:
                a[j][k] = 0

ans = "No"
if sum(a[0]) == 0:
    ans = "Yes"
elif sum(a[1]) == 0:
    ans = "Yes"
elif sum(a[2]) == 0:
    ans = "Yes"
elif a[0][0] + a[1][0] + a[2][0] == 0:
    ans = "Yes"
elif a[0][1] + a[1][1] + a[2][1] == 0:
    ans = "Yes"
elif a[0][2] + a[1][2] + a[2][2] == 0:
    ans = "Yes"
elif a[0][0] + a[1][1] + a[2][2] == 0:
    ans = "Yes"
elif a[0][2] + a[1][1] + a[2][0] == 0:
    ans = "Yes"
print(ans)
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)


### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)
a,b,c = map(int, input().split())
k = int(input())

lis = list(a,b,c)
lis.sort()
maxi = lis[-1]
print(lis[0]+lis[1]+k*maxi)

### FIXED CODE ###

a,b,c = map(int, input().split())
k = int(input())
 
lis = [a,b,c]
lis.sort()
maxi = lis[-1]
for i in range(k):
    maxi *= 2
print(lis[0]+lis[1]+maxi)
N, M = list(map(int, input().split(" ")))

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += dfs(edge, node, visited)
        
    return res

print(DFS(1, 0, []))

### FIXED CODE ###

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, prev, visited[:])
        
    return res

print(DFS(1, 0, []))
N = int(input())
def make_divisors(n):
    divisors = []
    divisors.append(1)
    ans=0
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            #divisors.append(i)
            #print(i)
            if(N%(i-1)==N//(i-1)):
                ans+=i
            if i != n // i:
                #divisors.append(n//i)
                if(N%(n//i-1)==N//(n//i-1)):
                    ans+=n//i-1
                #print(n//i)
    if(N%(N-1)==N//(N-1)):
        ans+=N-1
    print(ans)
    return divisors

res = make_divisors(N)
#print(res)

### FIXED CODE ###

N = int(input())
def make_divisors(n):
    divisors = []
    divisors.append(1)
    ans=0
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            #divisors.append(i)
            #print(i)
            if(N%(i-1)==N//(i-1)):
                ans+=i
            if i != n // i:
                #divisors.append(n//i)
                if(N%(n//i-1)==N//(n//i-1)):
                    ans+=n//i-1
                #print(n//i)
    if(N%(N-1)==N//(N-1)):
        ans+=N-1
    print(ans)
    return divisors

if(N==1):
    print(0)
else:
    res = make_divisors(N)
#print(res)
dp=[0]+[1<<20]*10000
n=int(input())
c=0
for i in range(1,n):
    if c==n-1:break
    a=int(input())
    c+=1
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

### FIXED CODE ###

dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        if dp[j]>dp[i-j]+a:dp[j]=dp[i-j]+a
        if dp[i-j]>dp[j]+a:dp[i-j]=dp[j]+a
print(dp[n//2])
from operator import mul
from functools import reduce

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for x1, y1 in xy:[1,2,3]
    for x2, y2 in xy:
        ans += ((x1-x2)**2+(y1-y2)**2)**0.5

ans = ans/n
print(ans)


### FIXED CODE ###

n=int(input())
xy=[list(map(int, input().split())) for _ in range(n)]

ans=0
for x1, y1 in xy:
	for x2, y2 in xy:
		ans+=((x1-x2)**2+(y1-y2)**2)**0.5
print(ans/n)
a = map(int, input().split())
if(a[0] >a[1]):
  print("No")
else:
  print("Yes")

### FIXED CODE ###


a = list(map(int, input().split()))
if(a[0] >a[1]):
  print("No")
else:
  print("Yes")
N = input()
A = list(map(int,input().split()))
count= 0
while(true):
    exist_odd = False
    for i in range(N):
        if(A[i]%2 != 0):
            exist_odd = True
    if(exist_odd == True):
        break
    for i in range(N):
        A[i] /= 2
    count += 1
print(count)


### FIXED CODE ###

str = input()
counter = 0
for i in range(len(str)):
    if(str[i]=="1"):
        counter += 1
print(counter)
import sys
n,m=map(int,input().split())
x =list(map(int,input().split()))

ans=0
if m==1:
    ans=0
else:


    x.sort()

    diff=[0]*(m-1)

    for i in range(m-1):
        diff[i]=x[i+1]-x[i]

    diff.sort()

    ans=0
    if n<=m:
        for i in range(m-n):
            ans+=diff[i]
    else:
        for i in range(diff.size()):
            ans+=diff[i]

print(ans)


### FIXED CODE ###

import sys
n,m=map(int,input().split())
x =list(map(int,input().split()))

ans=0
if n>=m:
    ans=0
else:
    x.sort()
    diff=[0]*(m-1)

    for i in range(m-1):
        diff[i]=x[i+1]-x[i]

    diff.sort()

    ans=0
    
    for i in range(m-n):
        ans+=diff[i]

print(ans)
H,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in[0]*H]
res=[]
for i in range(H):
    for j in range(W-1):
        if a[i][j]%2==1:
            res.append([i,j,i,j+1])
for i in range(H-1):
    if a[i][-1]%2==1:
        res.append([i,j,i+1,j])
print(len(res))
for x in res:
    print(*x)


### FIXED CODE ###

H,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in[0]*H]
res=[]
for i in range(H):
    for j in range(W-1):
        if a[i][j]%2==1:
            a[i][j]-=1
            a[i][j+1]+=1
            res.append([i,j,i,j+1])
for i in range(H-1):
    if a[i][-1]%2==1:
        a[i][-1]-=1
        a[i+1][-1]+=1
        res.append([i,W-1,i+1,W-1])
print(len(res))
for a,b,c,d in res:
    print(a+1,b+1,c+1,d+1)
x = int(input())
y = int(str(x)[:-2])
z = int(str(x)[-2:])
if x < 100:
    print(0)
    exit()
elif (y*5) < z:
    print(0)
    exit()
else:
    print(1)

### FIXED CODE ###

x = int(input())
if x < 100:
    print(0)
    exit()
else:
    y = int(str(x)[:-2])
    z = int(str(x)[-2:])
    if (y*5) < z:
        print(0)
        exit()
    else:
        print(1)
n,m = [int(x) for x in input().split()]
py = []
for i in range(m):
    p,y = [int(x) for x in input().split()]
    py.append([p,y,i+1])

def zero(num):
    return str(num).zfill(6)


if m == 1:
    print(zero(n)+zero(1))
else:
    year_py = sorted(py, key=lambda x: x[1])
    dic = {x: 0 for x in range(m)}

    for i in range(m):
        dic[year_py[i][0]] += 1
        year_py[i].append(dic[year_py[i][0]])
    yb_py = sorted(year_py, key=lambda x: x[2])

    for i in range(m):
        print(zero(yb_py[i][0]) + zero(yb_py[i][3]))

### FIXED CODE ###

n,m = [int(x) for x in input().split()]
py = []
for i in range(m):
    p,y = [int(x) for x in input().split()]
    py.append([p,y,i+1])

def zero(num):
    return str(num).zfill(6)


if m == 1:
    print(zero(py[0][0])+zero(1))
else:
    year_py = sorted(py, key=lambda x: x[1])
    dic = {str(x): 0 for x in range(1,n+1)}

    for i in range(m):
        dic[str(year_py[i][0])] += 1
        year_py[i].append(dic[str(year_py[i][0])])
    yb_py = sorted(year_py, key=lambda x: x[2])

    for i in range(m):
        print(zero(yb_py[i][0]) + zero(yb_py[i][3]))