Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# ABC 158 D
S=list(input())
Q=int(input())
inv=0
for _ in [0]*Q:
    s=input()
    if s=='1':
        inv+=1
    else:
        t,f,c=s.split()
        if ((f=='1') ^ (inv%2==1)):
            S=[c]+S
        else:
            S=S+[c]
if inv%2:
    S=S[::-1]
print(*S,sep='')

Fixed submission:
# ABC 158 D
from collections import deque

S=list(input())
q=deque(S)
Q=int(input())
inv=0
for _ in [0]*Q:
    s=input()
    if s=='1':
        inv+=1
    else:
        t,f,c=s.split()
        if ((f=='1') ^ (inv%2==1)):
            q.appendleft(c)
        else:
            q.append(c)
S=[]
if inv%2:
    while q:
        S.append(q.pop())
else:
    while q:
        S.append(q.popleft())
    
print(*S,sep='')

Buggy python submission (verdict: Time Limit Exceeded):
# ABC 158 D
S=list(input())
Q=int(input())
for _ in [0]*Q:
    s=input()
    if s=='1':
        s=int(s)
        S=S[::-1]
    else:
        t,f,c=s.split()
        if f=='1':
            S=[c]+S
        else:
            S=S+[c]
print(*S,sep='')

Fixed submission:
# ABC 158 D
from collections import deque

S=list(input())
q=deque(S)
Q=int(input())
inv=0
for _ in [0]*Q:
    s=input()
    if s=='1':
        inv+=1
    else:
        t,f,c=s.split()
        if ((f=='1') ^ (inv%2==1)):
            q.appendleft(c)
        else:
            q.append(c)
S=[]
if inv%2:
    while q:
        S.append(q.pop())
else:
    while q:
        S.append(q.popleft())
    
print(*S,sep='')
Buggy python submission (verdict: Runtime Error):
f=lambda:map(int,input().split())
N,M=f()
q=[list(f()) for _ in [0]*M]
res=-1
A=range(10**(N-1),10**N)
if N==1:A+=[0]
for i in A:
    for j in range(M):
        if str(i)[q[j][0]-1]!=str(q[j][1]):
            break
    else:
        res=i
        break
print(res)

Fixed submission:
f=lambda:map(int,input().split())
N,M=f()
q=[list(f()) for _ in [0]*M]
res=-1
A=list(range(10**(N-1),10**N))
if N==1:A=[0]+A
for i in A:
    for j in range(M):
        if str(i)[q[j][0]-1]!=str(q[j][1]):
            break
    else:
        res=i
        break
print(res)

Buggy python submission (verdict: Runtime Error):
f=lambda:map(int,input().split())
N,M=f()
q=[list(f()) for _ in [0]*M]
res=-1
A=range(10**(N-1),10**N)
if N==1:A+=[0]
for i in :
    for j in range(M):
        if str(i)[q[j][0]-1]!=str(q[j][1]):
            break
    else:
        res=i
        break
print(res)

Fixed submission:
f=lambda:map(int,input().split())
N,M=f()
q=[list(f()) for _ in [0]*M]
res=-1
A=list(range(10**(N-1),10**N))
if N==1:A=[0]+A
for i in A:
    for j in range(M):
        if str(i)[q[j][0]-1]!=str(q[j][1]):
            break
    else:
        res=i
        break
print(res)
Buggy python submission (verdict: Runtime Error):
# Union Find

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
check=[[0]*(N+1) for _ in [0]*(N+1)]
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    check[b][a]==1
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    check[d][c]==1
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])

Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
p=list(map(int,input().split()))

res=0
for i in range(N-K+1):
    res=max(res,(sum(p[i:i+K])+K)/2)
print(res)

Fixed submission:
N,K=map(int,input().split())
p=list(map(int,input().split()))

res=0
s=sum(p[:K])
for i in range(N-K+1):
    res=max(res,(s+K)/2)
    if i!=N-K:
        s=s+p[i+K]-p[i]
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H]) 

Fixed submission:
# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])

Buggy python submission (verdict: Runtime Error):
#E
H,N=map(int,input().split())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
    
memo=[0]*(H+10)
def dpinit(H):
    for i in range(H):
        memo[H]=min([dp(H-A[i])+B[i] for i in range(N)])
    
def dp(H):
    if H<=0:
        return 0
    else:
        if memo[H]==0:
            memo[H]=min([dp(H-A[i])+B[i] for i in range(N)])
        return memo[H]
    
dpinit(int(H//100))
print(dp(H))

Fixed submission:
# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])

Buggy python submission (verdict: Runtime Error):
#E
H,N=map(int,input().split())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
    
memo=[0]*(H+10)
def dp(H):
    if H<=0:
        return 0
    else:
        if memo[H]==0:
            memo[H]=min([dp(H-A[i])+B[i] for i in range(N)])
        return memo[H]

print(dp(H))

Fixed submission:
# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])
Buggy python submission (verdict: Runtime Error):
N=input()
alp='abcdefghijklmnopqrstuvwxyz'
print(alp[alp.find(N)+1])

Fixed submission:
N=input()
alp='abcdefghijklmnopqrstuvwxyz'
print(alp[alp.find(N)+1])
Buggy python submission (verdict: Time Limit Exceeded):
infty=10**5
memo_of_num=[]
for i in range(infty):
    memo_of_num.append([0]*infty)
def numOfPath(n,m,l=[]):
    if (n,m) in l:
        memo_of_num[n][m]=0
    elif n*m==0:
        memo_of_num[n][m]=1
    else:
        memo_of_num[n][m]=numOfPath(n-1,m,l)+numOfPath(n,m-1,l)
    return memo_of_num[n][m]

def nCk(n,k):
    return numOfPath(n-k,k)


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s1=0
for i in range(N-K+1):
    s1+=A[i]*nCk(N-(i+1),K-1)
A=A[::-1]
s2=0
for i in range(N-K+1):
    s2+=A[i]*nCk(N-(i+1),K-1)
print(s1-s2)

Fixed submission:
mod = 10**9 + 7
MAX=10**6
fac,finv,inv=[0]*MAX,[0]*MAX,[0]*MAX

def nCkinit(mod):
    fac[0]=finv[0]=1
    fac[1]=finv[1]=inv[1]=1
    for i in range(2,MAX):
        fac[i]=fac[i-1]*i % mod
        inv[i]=mod-inv[mod%i] *(mod//i) %mod
        finv[i]=finv[i-1]*inv[i] % mod
        
def modnCk(n,k,mod):
    if n<k:return 0
    if n<0 or k<0:return 0
    else:
        return fac[n]*(finv[n-k]*finv[k]% mod) % mod
    
nCkinit(mod)

###
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s1=s2=0
for i in range(N-K+1):
    s1+=(A[i]*modnCk(N-(i+1),K-1,mod))%mod
    s2+=(A[N-(i+1)]*modnCk(N-(i+1),K-1,mod))%mod
print((s1-s2)%mod)

Buggy python submission (verdict: Time Limit Exceeded):
infty=10**5
memo_of_num=[]
for i in range(infty):
    memo_of_num.append([0]*infty)
def numOfPath(n,m,l=[]):
    if (n,m) in l:
        memo_of_num[n][m]=0
    elif n*m==0:
        memo_of_num[n][m]=1
    else:
        memo_of_num[n][m]=numOfPath(n-1,m,l)+numOfPath(n,m-1,l)
    return memo_of_num[n][m]

def nCk(n,k):
    return numOfPath(n-k,k)


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s1=0
for i in range(N-K+1):
    s1+=A[i]*nCk(N-(i+1),K-1)
A=A[::-1]
s2=0
for i in range(N-K+1):
    s2+=A[i]*nCk(N-(i+1),K-1)
print(s1-s2)

Fixed submission:
mod = 10**9 + 7
MAX=10**6
fac,finv,inv=[0]*MAX,[0]*MAX,[0]*MAX

def nCkinit(mod):
    fac[0]=finv[0]=1
    fac[1]=finv[1]=inv[1]=1
    for i in range(2,MAX):
        fac[i]=fac[i-1]*i % mod
        inv[i]=mod-inv[mod%i] *(mod//i) %mod
        finv[i]=finv[i-1]*inv[i] % mod
        
def modnCk(n,k,mod):
    if n<k:return 0
    if n<0 or k<0:return 0
    else:
        return fac[n]*(finv[n-k]*finv[k]% mod) % mod
    
nCkinit(mod)

###
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s1=s2=0
for i in range(N-K+1):
    s1+=(A[i]*modnCk(N-(i+1),K-1,mod))%mod
    s2+=(A[N-(i+1)]*modnCk(N-(i+1),K-1,mod))%mod
print((s1-s2)%mod)
Buggy python submission (verdict: Runtime Error):
s=input();n=len(s)-1;print(sum(s[i]!=s[n-i]for i in range(n+1))//2)s=input();n=len(s)-1;print(sum(s[i]!=s[n-i]for i in range(n+1))//2)

Fixed submission:
s=input();print(sum(s[i]!=s[len(s)-i-1] for i in range(len(s)))//2)
Buggy python submission (verdict: Runtime Error):
# ABC 147 D

N=int(input())
A=list(map(int,input().split()))
res=0
p=10**9+7

bits=[0]*71
for a in A:
    j=0
    while a>>j:
        if (a>>j)&1:
            bits[j]+=1
        j+=1

t=0
n=70
while 1:
    if bits[n]!=0:
        break
    n-=1

for a in A:
    j=0
    while j<=n:
        if (a>>j)&1:
            res+=((2**j)*(N-bits[j]))%p
        else:
            res+=((2**j)*bits[j])%p
        j+=1
    t=res
print((res*500000004)%p)

Fixed submission:
# ABC 147 D

N=int(input())
A=list(map(int,input().split()))
res=0
p=10**9+7

bits=[0]*71
for a in A:
    j=0
    while a>>j:
        if (a>>j)&1:
            bits[j]+=1
        j+=1

t=0
n=70
while n>=0:
    if bits[n]!=0:
        break
    n-=1

for a in A:
    j=0
    while j<=n:
        if (a>>j)&1:
            res+=((2**j)*(N-bits[j]))%p
        else:
            res+=((2**j)*bits[j])%p
        j+=1
    t=res
print((res*500000004)%p)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
    A[-1]=A[-1]//2
    A.sort()
print(sum(A))

Fixed submission:
import heapq 

N,M=map(int,input().split())
A=[-a for a in list(map(int,input().split()))]
heapq.heapify(A)
for _ in [0]*M:
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))
    
res=0
for i in range(N):
    a=heapq.heappop(A)
    res+=-a
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A[A.index(max(A))]=A[A.index(max(A))]//2
print(sum(A))

Fixed submission:
import heapq 

N,M=map(int,input().split())
A=[-a for a in list(map(int,input().split()))]
heapq.heapify(A)
for _ in [0]*M:
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))
    
res=0
for i in range(N):
    a=heapq.heappop(A)
    res+=-a
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
s=input()
flg=False
for i in range(N//2-1,-1,-1):
    # 長さ
    if flg:
        break
    for j in range(0,N-i-1):
        if flg:
            break
        # 開始位置
        tmp=s[j:j+i+1]
        s2=s[j+i+1:]
        if tmp in s2:
            print(len(tmp))
            flg=True
if not flg:
    print(0)

Fixed submission:
N=int(input())
S=input()

l,r=0,1
res=0
def check(l,r):
    #半閉区間[l,r)
    if not l<r:
        return False
    t=S[l:r]
    s=S[r:]
    n=(r-l)
    for i in range(len(s)-n+1):
        if s[i:i+n]==t:
            return True
    return False
        


while l<N and r<N:
    if r==l:
        r+=1
    if check(l,r):
        res=max(r-l,res)
        r+=1
    else:
        l+=1
    
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
setT=list(set(T))    
    
if set(T)<=set(S):
    i=0
    j=0
    while 1:
        if S[i%len(S)]==T[j]:
            j+=1
        if j==len(T):
            break
        i+=1
    print(i+1)
else:
    print(-1)

Fixed submission:
from bisect import bisect_right as br
S=input()
T=input()

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        if seqT:
            a=seqT[-1]
        else:
            a=-1
        j=br(ALF[i],a)
        seqT.append(ALF[i][j%len(ALF[i])])
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
setT=set(T)
flg=True
for t in setT:
    if not t in S:
        flg=False
if flg:
    i=0
    j=0
    while 1:
        if S[i%len(S)]==T[j]:
            j+=1
        if j==len(T):
            break
        i+=1
    print(i+1)
else:
    print(-1)

Fixed submission:
from bisect import bisect_right as br
S=input()
T=input()

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        if seqT:
            a=seqT[-1]
        else:
            a=-1
        j=br(ALF[i],a)
        seqT.append(ALF[i][j%len(ALF[i])])
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC129 E

L=input()[::-1]
A=[0]*(len(L)+1)
B=[0]*(len(L)+1)
p=10**9+7

A[0],B[0]=1,2
res=0
tmp=1
for i in reversed(range(len(L))):
    if L[i]=='1':
        res=(res+tmp*3**i)%p
        tmp=(2*tmp)%p
print((res+tmp)%p) 

Fixed submission:
# ABC129 E

L=input()
N=len(L)
p=10**9+7

def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p


res=0
tmp=1
for i in reversed(range(N)):
    if L[N-1-i]=='1':
        res=(res+tmp*pow_k(3,i,p))%p
        tmp=(2*tmp)%p
print((res+tmp)%p)
Buggy python submission (verdict: Runtime Error):
N=int(input())
G=[[0]*(N+1) for  _ in [0]*(N+1)]
res=[0]*(N+1)

for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u][v]=w
    G[v][u]=w
    
    
stack=[]
stack.append(1)
res[1]=1
while stack:
    r=stack.pop()
    for k in range(N+1):
        if G[r][k]>0 and res[k]==0:
            stack.append(k)
            if G[r][k]%2:
                res[k]=-res[r]
            else:
                res[k]=res[r]
for i in res[1:]:
    print((i+1)//2)
        
        
            
    
    
    
    
    

Fixed submission:
N=int(input())
G=[[] for _ in [0]*(N+1)]
for _ in [0]*(N-1):
    u,v,w=map(int,input().split())
    G[u].append((v,w))
    G[v].append((u,w))

c=[0]*(N+1)
stack=[1]
c[1]=1
while stack:
    r=stack.pop()
    for nr,nw in G[r]:
        if c[nr]==0:
            stack.append(nr)
            if nw%2:
                c[nr]=-c[r]
            else:
                c[nr]=c[r]
for i in c[1:]:
    print((i+1)//2)
Buggy python submission (verdict: Runtime Error):
#frog
n=int(input())
h=[10**10]+list(map(int,input().split()))+[10**10]*10
def dp(i):
    if i<=1:
        return 0
    else:
        return min([dp(i-1)+abs(h[i]-h[i-1]),dp(i-2)+abs(h[i]-h[i-2])])
print(dp(n))

Fixed submission:
#frog
H=10**10
n=int(input())
h=list(map(int,input().split()))+[H]*10
dp=[0]*(n+10)
for i in range(1,n+1):
    dp[i]=min([dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])])
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
X=[[] for x in range(N+1)]
city=[]
for i in range(M):
    P,Y=map(int,input().split())
    city.append((P,Y))
    X[P].append(Y)
S=[0]*(N+1)
for p,y in city:
    if S[p]==0:
        X[p].sort()
        S[p]=1
    num=X[p].index(y)+1
    print("%06d"%p+"%06d"%num)

Fixed submission:
# ABC113 D 

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

P=[[] for _ in [0]*(N+1)]

for i in range(M):
    p,y=map(int,input().split())
    P[p].append((y,i))
    
from bisect import bisect_left as bl

res=[]
for p in range(N+1):
    Y=P[p][:]
    if not Y:
        continue
    
    sortY=sorted(list(set(Y)))
        
    zatY=[]
    for t_y in Y:
        zatY.append(bl(sortY,t_y))
    
    for index in zatY:
        y,i=sortY[index]
        num=10**12+p*10**6+index+1
        res.append((str(num)[1:],i))

res=[y for y,i in sorted(res,key=lambda x:x[1])]
print(*res,sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
X=[[] for x in range(N+1)]
city=[]
for i in range(M):
    P,Y=map(int,input().split())
    city.append((P,Y))
    X[P].append(Y)
X=[sorted(i) for i in X]
for p,y in city:
    num=X[p].index(y)+1
    print("%06d"%p+"%06d"%num)

Fixed submission:
# ABC113 D 

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

P=[[] for _ in [0]*(N+1)]

for i in range(M):
    p,y=map(int,input().split())
    P[p].append((y,i))
    
from bisect import bisect_left as bl

res=[]
for p in range(N+1):
    Y=P[p][:]
    if not Y:
        continue
    
    sortY=sorted(list(set(Y)))
        
    zatY=[]
    for t_y in Y:
        zatY.append(bl(sortY,t_y))
    
    for index in zatY:
        y,i=sortY[index]
        num=10**12+p*10**6+index+1
        res.append((str(num)[1:],i))

res=[y for y,i in sorted(res,key=lambda x:x[1])]
print(*res,sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
X=[[] for x in range(N)]
city=[]
for i in range(M):
    P,Y=map(int,input().split())
    P-=1
    city.append((P,Y))
    X[P].append(Y)
X=[sorted(i) for i in X]
for p,y in city:
    num=X[p].index(y)+1
    p+=1
    print("%06d"%p+"%06d"%num)

Fixed submission:
# ABC113 D 

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

P=[[] for _ in [0]*(N+1)]

for i in range(M):
    p,y=map(int,input().split())
    P[p].append((y,i))
    
from bisect import bisect_left as bl

res=[]
for p in range(N+1):
    Y=P[p][:]
    if not Y:
        continue
    
    sortY=sorted(list(set(Y)))
        
    zatY=[]
    for t_y in Y:
        zatY.append(bl(sortY,t_y))
    
    for index in zatY:
        y,i=sortY[index]
        num=10**12+p*10**6+index+1
        res.append((str(num)[1:],i))

res=[y for y,i in sorted(res,key=lambda x:x[1])]
print(*res,sep='\n')
Buggy python submission (verdict: Runtime Error):
#112D
N,M=map(int,input().split())
for i in list(range(1,M//N+1))[::-1]:
    flag=M-N*i
    if flag%i==0 and flag>=0:
        print(i)
        break

Fixed submission:
#112D
N,M=map(int,input().split())
B=int((M**(1/2))//1)
A=[M//i for i in range(1,int((M**(1/2)+1)//1))]+list(range(1,B))
A.sort(reverse=True)
for i in A:
    flag=M-N*i
    if flag%i==0 and flag>=0:
        print(i)
        break
Buggy python submission (verdict: Runtime Error):
#C
S=input()
K=int(input())
num='23456789'
if S[0]!='1':
    print(1)
else:
    n=1
    while True:
        if n==len(S):
            n-=1
            break
        elif S[n]!='1':
            break
        n+=1
if K-1<n:
    print(1)
else:
    print(int(S[n]))

Fixed submission:
#C
S=input()
K=int(input())
num='23456789'
if S[0]!='1':
    print(int(S[0]))
else:
    n=1
    while True:
        if n==len(S):
            n-=1
            break
        elif S[n]!='1':
            break
        n+=1
    if K-1<n:
        print(1)
    else:
        print(int(S[n]))

Buggy python submission (verdict: Runtime Error):
#C
S=input()
K=int(input())
num='23456789'
if S[0]!='1':
    print(1)
else:
    n=1
    while True:
        if n==len(S):
            n-=1
            break
        elif S[n]!='1':
            break
        n+=1
if K-1<n:
    print(1)
else:
    print(S[n])

Fixed submission:
#C
S=input()
K=int(input())
num='23456789'
if S[0]!='1':
    print(int(S[0]))
else:
    n=1
    while True:
        if n==len(S):
            n-=1
            break
        elif S[n]!='1':
            break
        n+=1
    if K-1<n:
        print(1)
    else:
        print(int(S[n]))
Buggy python submission (verdict: Runtime Error):
D,G=map(int,input().split())
p,c=[0]*D,[0]*D
cell=[]
for i in range(D):
    p[i],c[i]=map(int,input().split())
    cell.append([-1]*102)

m=0,0,0
mondai=[]
for i in range(2**D,2**(D+1)):
    s=(bin(i))[3:]
    a,b=0,0
    for j in range(D):
        if s[j]=='1':
            a,b=a+p[j],b+100*(j+1)*p[j]+c[j]
        else:
            m=j
    if G<b:
        mondai.append(a)
    if G-p[m]*100*(m+1)<b<G:
        ad=(G-b)//(100*(m+1))
        mondai.append((a+ad))
print(min(mondai))

Fixed submission:
from math import ceil
D,G=map(int,input().split())
p,c=[0]*D,[0]*D
for i in range(D):
    p[i],c[i]=map(int,input().split())

m=0
mondai=[]
for i in range(2**D,2**(D+1)):
    s=(bin(i))[3:]
    a,b=0,0
    for j in range(D):
        if s[j]=='1':
            a,b=a+p[j],b+100*(j+1)*p[j]+c[j]
        else:
            m=j
    if G<=b:
        mondai.append(a)
    if G-p[m]*100*(m+1)<b<G:
        ad=ceil((G-b)/(100*(m+1)))
        mondai.append((a+ad))
print(min(mondai))