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

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)


### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
### BUGGY CODE ###

mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
from functools import lru_cache
@lru_cache(maxsize=10**8)
def dp(i, j):
    n = min(i+j+1, N)
    if i+j == N*2:
        return 1
    res = 0
    s = Sum[n]
    if i<s:
        res+=dp(i+1, j)
    if j<2*n-s:
        res+=dp(i, j+1)
    return res%mod
print(dp(0, 0))

### FIXED CODE ###

mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
dp = [[0]*(N*2+1) for _ in range(N*2+1)]
for i in range(N*2+1)[::-1]:
    for j in range(N*2+1)[::-1]:
        if i+j == N*2:
            dp[i][j] = 1
            continue
        n = min(i+j+1, N)
        s = Sum[n]
        if i<s:
            dp[i][j]+=dp[i+1][j]
        if 2*n-s>j:
            dp[i][j]+=dp[i][j+1]
        dp[i][j]%=mod
print(dp[0][0])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=0
for i in range(N):
    for j in range(i+1,N):
        if a[i]==j+1 and a[j]==i+1:
            b+=1
print(b)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=0
for i in range(N):
    if i+1==a[a[i]-1]:
        b+=1
print(b//2)
### BUGGY CODE ###

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

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

ans = 1
INF = 1000000000000000000

# for a in A:
#     ans *= a

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
ans = prod(A)

if ans > INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
INF = 1000000000000000000

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

for a in A:
    ans *= a
    if ans > INF:
        print(-1)
        exit()

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

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[[0,0] for i in range(w)] for j in range(h)]
for i in range(h):
    k=0
    while k<w:
        cnt=0
        if s[i][k]==".":
            j=k
            while k<w and s[i][k]=="." and a[i][k][0]==0:
                k+=1
                cnt+=1
            for x in range(j,k):
                a[i][x][0]=cnt
        else:
            k+=1
for i in range(w):
    k=0
    while k<h:
        cnt=0
        if s[k][i]==".":
            j=k
            while k<h and s[k][i]=="." and a[k][i][1]==0:
                k+=1
                cnt+=1
            for x in range(j,k):
                a[x][i][1]=cnt
        else:
            k+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j][0]+a[i][j][1])
print(ans-1)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[0]*w for j in range(h)]
b=[[0]*w for j in range(h)]
for i in range(h):
    k=0
    rep=0
    while k<w:
        cnt=0
        if s[i][k]==".":
            j=k
            while k<w and s[i][k]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                a[i][x]=cnt
        else:
            k+=1
for i in range(w):
    k=0
    while k<h:
        cnt=0
        if s[k][i]==".":
            j=k
            while k<h and s[k][i]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                b[x][i]=cnt
        else:
            k+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j]+b[i][j])
print(ans-1)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(2, n+1):
    ans *= i
print(ans % (10**9+7))


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(2, n+1):
    ans = ans * i % (10**9+7)
print(ans % (10**9+7))
### BUGGY CODE ###

def getval():
    r,c,k = map(int,input().split())
    item = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        ri,ci,vi = map(int,input().split())
        item[ri-1][ci-1] = vi
    return r,c,k,item

def main(r,c,k,item):
    #DP containing the information of max value given k items picked in i,j
    dp = [[[0,0,0,0] for i in range(c)] for i in range(r)]
    inititem = item[0][0]
    dp[0][0] = [0,inititem,inititem,inititem]
    for i in range(1,r):
        cur = item[i][0]
        init = dp[i-1][0][3]
        for j in range(4):
            if j:
                dp[i][0][j] += init + cur
            else:
                dp[i][0][j] += init

    for i in range(1,c):
        cur = item[0][i]
        prev = dp[0][i-1]
        for j in range(1,4):
            dp[0][i][j] = max(prev[j-1]+cur,prev[j])

    for i in range(1,r):
        for j in range(1,c):
            left = dp[i-1][j]
            down = dp[i][j-1]
            cur = item[i][j]
            dp[i][j][0] = max(left[3],down[0])
            for k in range(1,4):
                dp[i][j][k] = max(max(left[3],down[k-1])+cur,down[k])

    print(max(dp[r-1][c-1]))   

if __name__=="__main__":
    r,c,k,item = getval()
    main(r,c,k,item) 

### FIXED CODE ###

from copy import deepcopy

def getval():
    r,c,k = map(int,input().split())
    item = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        ri,ci,vi = map(int,input().split())
        item[ri-1][ci-1] = vi
    return r,c,k,item

def main(r,c,k,item):
    #DP containing the information of max value given k items picked in i,j
    prev = [[0 for i in range(4)]]
    inititem = item[0][0]
    prev[0] = [0,inititem,inititem,inititem]
    for i in range(1,r):
        initval = prev[i-1][3]
        temp = []
        cur = item[i][0]
        for j in range(4):
            temp.append(initval)
        for j in range(1,4):
            temp[j] += cur
        prev.append(temp)

    for j in range(1,c):
        init = deepcopy(prev[0])
        for i in range(1,4):
            init[i] = max(prev[0][i],prev[0][i-1]+item[0][j])
        curcol = [init]
        for i in range(1,r):
            cur = item[i][j]
            left = curcol[-1]
            down = prev[i]
            temp = [max(left[3],down[0])]
            for k in range(1,4):
                temp.append(max(max(left[3],down[k-1])+cur,down[k]))
            curcol.append(temp)
        prev = curcol
            
    print(max(prev[-1]))
           
if __name__=="__main__":
    r,c,k,item = getval()
    main(r,c,k,item)
### BUGGY CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))

    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    N = int(input())
    P = list(map(int,input().split()))

    #result = list()

    minimum = P[0]
    count = 1
    for i in range(N):
        if(minimum > P[i]):
            minimum = P[i]
            count += 1
    print(count)
#        Pj = list(P[j] for j in range(i+1))
        #print(Pj)
        #Pj = P[0:i+1]
#        min_P = min(Pj)
#        result.append(min_P)
#        print(min_P)
#        if(P[i] == min_P):
#            count += 1

    '''
    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)
    '''

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

# 初期入力
N,M = (int(x) for x in input().split())
A = [int(input()) for i in range(M)]


#
mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] # % mod_9
print(kotae )

### FIXED CODE ###

# 初期入力
N,M = (int(x) for x in input().split())
A = set([int(input()) for i in range(M)])


#
mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] # % mod_9
print(kotae )
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  for i in range(q):
    l,r = (int(m) for m in input().split())
    if l == r:
      print(0)
    else:
      ans = 0
      for j in range((r-l)//d):
        leftx,lefty = query[(l-1)+j*d]
        rightx,righty = query[(l-1)+(j+1)*d]
        ans += abs(rightx-leftx)+abs(righty-lefty)
      print(ans)
  
solve()

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  
  for i in range(q):
    l,r = (int(m) for m in input().split())
    print(distance[r-1]-distance[l-1])
  
solve()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
a_solution_dic_at_k = {}
for key in a_dic:
    a_solution_dic[key] = int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)


for k, ak in enumerate(a_list):
    sum_select = 0
    sum_select += int((a_dic[ak]-1) * (a_dic[ak]-2) / 2)
    for key in a_solution_dic:
        if key != ak:
            sum_select += a_solution_dic[key]


    print(sum_select)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###

n = int(input())
a_lst = []
for i in range(n):
    a = int(input())
    a_lst.append(a)

for i in range(n):
    if i == 0:
        tmp = a_lst[i+1:]
    elif i == n-1:
        tmp = a_lst[:i]
    else:
        tmp = a_lst[:i] + a_lst[i+1:]
    print(max(tmp))

### FIXED CODE ###

n = int(input())
a_lst = []
for i in range(n):
    a = int(input())
    a_lst.append(a)

sorted_a_lst = sorted(a_lst)
max_a = sorted_a_lst[-1]

for a in a_lst:
    if a == max_a:
        print(sorted_a_lst[-2])
    else:
        print(max_a)
### BUGGY CODE ###

import bisect as bi
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
L=[]
for i in range(M):
    l=list(map(int,input().split()))
    L.append(l)
L=sorted(L,reverse=True,key=lambda x: x[1])
x=0
for i in range(M):
    if bi.bisect_left(A,L[i][1])==0:
        break
    if len(A)==0:
        break
    m=min(L[i][0],bi.bisect_left(A,L[i][1]))
    del A[0:m]
    x+=m*L[i][1]
print(x+sum(A))




### FIXED CODE ###

from operator import itemgetter
l = list(map(int, input().split()))
N = l[0]
M = l[1]
A = list(map(int, input().split()))
B = []
for i in range(M):
    b = list(map(int, input().split()))
    B.append(b)
A = sorted(A)
B = sorted(B, key=lambda x: x[1])
m = 0
s = 0
for i in range(M):
    i = M-1-i
    if B[i][0]+m <= N-1:

        if A[B[i][0]+m] <= B[i][1]:
            m = m+B[i][0]
            s += B[i][1]*B[i][0]
        else:
            if A[m] <= B[i][1]:
                for l in range(m, N):
                    if A[l] >= B[i][1]:
                        s += B[i][1]*(l-m)
                        m = l
                        break
            else:
                break
    else:
        if A[N-1] <= B[i][1]:
            s = s+B[i][1]*(N-m)
            m = N
            break
        else:
            if A[m] <= B[i][1]:
                for l in range(m, N):
                    if A[l] >= B[i][1]:
                        s += B[i][1]*(l-m)
                        m = l
                        break
            else:
                break
if m < N:
    for i in range(m, N):
        s += A[i]
print(s)
### BUGGY CODE ###

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

ans = 1
list.sort(a, reverse = True)
for i in range(len(a)):
    if 0 in a:
        ans =0
        break

    ans = ans * a[i]
    if ans >10**18:
        break


if ans >10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
list.sort(a, reverse = True)
ones = a.count(1)
for i in range(len(a)-ones):
    if 0 in a:
        ans =0
        break
    ans = ans * a[i]
    if ans >10**18:
        break

if ans >10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from operator import itemgetter
n,m=map(int,input().split())
wa=0
ac=0
ig=0
l=[(input().split()) for _ in range(m)]
l=sorted(l, key=itemgetter(0))
ll=sorted(l, key=itemgetter(0))

for t in l:
  c,r=t[0],t[1]
  if c == ig:
    continue
  
  if [c,'AC'] not in l:
    continue
  
  if r == 'WA':
    wa+=1
  elif r == 'AC':
    ac+=1
    ig=c
  del ll[0]
print(ac,wa)

### FIXED CODE ###

n,m=map(int,input().split())
l=[[] for _ in range(n)]
for _ in range(m):
  a,b=input().split()
  l[int(a)-1].append(b)
  
wacnt=0
accnt=0

for rl in l:
  cnt = 0
  for r in rl:
    if r == 'WA':
      cnt+=1
    elif r == 'AC':
      wacnt+=cnt
      accnt+=1
      break
      
print(accnt, wacnt)
### BUGGY CODE ###

S = input()
T = input()
cnt = []
ans = 1
fis1 = [index for index, word in enumerate(S) if word == S[0]]
fis2 = [index for index, word in enumerate(T) if word == T[0]]
 
if fis1 != fis2:
    ans = 0
else:
    for i in range(len(S)):
        if i not in fis1:
            kensa1 = [index for index, word in enumerate(S) if S[i] == word]
            kensa2 = [index for index, word in enumerate(T) if T[i] == word]
            if kensa1 != kensa2:
                ans = 0
                break
            else:
                fis1.append(kensa1)
          
    
print('Yes' if ans == 1 else 'No')

### FIXED CODE ###

S = input()
T = input()

used = []
res  = []

for i in range(len(S)):
    if S[i] not in used:
        used.append(S[i])
    res.append(used.index(S[i]))

#print(used)
#print(res)
used = []
ret = []

for i in range(len(T)):
    if T[i] not in used:
        used.append(T[i])
    ret.append(used.index(T[i]))

if res == ret:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# import math
# import fractions
# import numpy as np

MOD = 10 ** 9 + 7

def solve(N, A):
    # for i, a in enumerate(A):
    #     A[i] = bin(a)
    # print(A)
    
    ans = 0
    for i in range(N - 1):
        for j in range(i+1, N):
          ans += (A[i] ^ A[j]) % MOD

    return ans % MOD

# S = input()
N = int(input())
# H, N = map(int, input().split())
A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
# A = []
# B = []
# for _ in range(N):
#     a, b = list(map(int, input().split()))
#     A.append(a)
#     B.append(b)

print(solve(N, A))


### FIXED CODE ###

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

MOD = 10 ** 9 + 7
ans = 0
m = 1
ans = 0
for _ in range(60):
    one_count = sum(a & m for a in aaa)
    one_count //= m
    zero_count = n - one_count
    ans = (ans + one_count * zero_count * m) % MOD
    m *= 2
        
print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
s = input()
ans = 0

for i in range(1000):
    i = str(i).zfill(3)
    
    cnt = 0
    for ss in s:
        if cnt == 0:
            if ss==i[0]:
                cnt += 1
                continue
        elif cnt == 1:
            if ss==i[1]:
                cnt += 1
                continue
        else:
            if ss==i[2]:
                ans += 1
                break

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0

for i in range(1000):
    i = str(i).zfill(3)

    first = s.find(i[0])
    if first == -1:
        continue

    second = s.find(i[1], first+1)
    if second == -1:
        continue

    third = s.find(i[2], second+1)

    if third != -1:
        ans += 1

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

n,m = map(int,input().split())
arr = []
for i in range(m):
	ls = list(map(int,input().split()))
	arr.append(ls)

def st(a):
	b = list(str(a))
	while len(b) <= 5:
		b.insert(0,'0')
	c= ''.join(b)
	return c

for y in arr:
	k = 1
	for j in arr:
		if y[0] == j[0] and y[1] > j[1]:
			k += 1
			
	print('{}{}'.format(st(y[0]), st(k)))




### FIXED CODE ###


n,m = map(int,input().split())
arr = []
for i in range(m):
	ls = list(map(int,input().split()))+[i]
	arr.append(ls)

arr.sort(key=lambda x:x[1])

def st(a):
	b = list(str(a))
	while len(b) <= 5:
		b.insert(0,'0')
	c= ''.join(b)
	return c

dic = {}
for j in range(m):
	if arr[j][0] in dic:
		dic[arr[j][0]] += 1
		arr[j] += [dic[arr[j][0]]]
	else:
		dic[arr[j][0]] = 1
		arr[j] += [dic[arr[j][0]]]

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

for y in range(m):
	print('{}{}'.format(st(arr[y][0]), st(arr[y][3])))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    return mx

print(find(W, 0))


### FIXED CODE ###

import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

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

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

res = 0
for i in a:
    cnt = 0
    cnt += a.count(i)
    cnt += a.count(i-1)
    cnt += a.count(i+1)
    res = max(res,cnt)
print(res)

### FIXED CODE ###

from collections import Counter

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

c = [0 for _ in range(10**5+3)]

for i in a:
    c[i-1] += 1
    c[i+1] += 1
    c[i] += 1
print(max(c))
### BUGGY CODE ###

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


def ca(n):
    array = [0]*(N-n+1)
    array[0] = sum([A[i] for i in range(n)])
    for i in range(1,N - n + 1):
        array[i] = array[i - 1] + A[n + i - 1] - A[i-1]
    return array


count = 0
for j in range(1, N+1):
    count += sum([1 if k == 0 else 0 for k in ca(j)])

print(count)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ca = [A[0]] + [0]*(N-1)

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

count = 1
number = 0
number += ca.count(0)
sca = sorted(ca) + ['hoge']
for i in range(1,N+1):
    if sca[i] == sca[i-1]:
        count += 1
    else:
        number += count*(count - 1)/2
        count = 1


print(int(number))