Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int, input().split())

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

mod = 10**9+7
fact = [1]
for n in range(1, N+1):
    fact.append( fact[-1] * n % mod)
from copy import deepcopy as dcpy

def solve(S, X):
    n = len(S)

    if all( X < s for s in S):
        return fact[n] * X % mod
    if n == 1:
        return X % S[0] % mod

    ans = 0

    def popi(S,i):
        return S[:i] + S[i+1:]
    # s_holder = [ dcpy(S) for _ in range(n)]
    for i,s in enumerate(S):
        new_x = X % s
        # s_holder[i].pop(i)
        # ans = (ans + solve(s_holder[i], new_x)) % mod
        ans = (ans + solve(popi(S,i), new_x)) % mod
    return ans % mod

print( solve(S, X) % mod )
        




Fixed submission:
N,X = map(int, input().split())
S = list(map(int,input().split()))

S.sort(reverse=True)
mod = 10**9+7
dp = [ [0] * (10**5+1) for _ in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for j in range(0,10**5+1):
        dp[i+1][j] += dp[i][j] * (N-1-i) % mod
        dp[i+1][j% S[i]] += dp[i][j] 

        dp[i+1][j] %= mod
        dp[i+1][j%S[i]] %= mod
ans = 0
for j in range(0,10**5+1):
    ans = (ans + dp[N][j] * j % mod ) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int, input().split())

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

mod = 10**9+7
fact = [1]
for n in range(1, N+1):
    fact.append( fact[-1] * n % mod)
from copy import deepcopy as dcpy

def solve(S, X):
    n = len(S)

    if all( X < s for s in S):
        return fact[n] * X % mod
    if n == 1:
        return X % S[0] % mod

    ans = 0

    s_holder = [ dcpy(S) for _ in range(n)]
    for i,s in enumerate(S):
        new_x = X % s
        s_holder[i].pop(i)
        ans = (ans + solve(s_holder[i], new_x)) % mod
    return ans % mod

print( solve(S, X) % mod )
        




Fixed submission:
N,X = map(int, input().split())
S = list(map(int,input().split()))

S.sort(reverse=True)
mod = 10**9+7
dp = [ [0] * (10**5+1) for _ in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for j in range(0,10**5+1):
        dp[i+1][j] += dp[i][j] * (N-1-i) % mod
        dp[i+1][j% S[i]] += dp[i][j] 

        dp[i+1][j] %= mod
        dp[i+1][j%S[i]] %= mod
ans = 0
for j in range(0,10**5+1):
    ans = (ans + dp[N][j] * j % mod ) % mod

print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input()) 
clist=[-1]
mod=10**9+7
for i in range(N):
  t=int(input())
  if t==clist[-1]:
    continue
  clist.append(t)
  
colorlast=[-1]*(3*10**5)
poslp=[-1]*(N+2)

for e,c in enumerate(clist,1):
  if colorlast[c]!=-1:
    poslp[e]=colorlast[c]
    colorlast[c]=e
  else:
    colorlast[c]=e

dp=[0]*(N+1)
dp[0]=1
for e,c in enumerate(clist,1):
  if poslp[e]!=-1:
    dp[e]=(dp[e-1])%mod
  else:
    dp[e]=(dp[e-1]+dp[poslp[e]])%mod
print(dp[len(clist)]%mod)
    


Fixed submission:
N=int(input()) 
clist=[-1]
mod=10**9+7

for i in range(N):
  t=int(input())
  if t==clist[-1]:
    continue
  clist.append(t)

del clist[0]
N = len(clist)

# print(clist)
colorlast=[-1]*(3*10**5)
poslp=[-1]*(N+1)

for e,c in enumerate(clist,1):
  if  colorlast[c]  !=  -1:
    poslp[e]=colorlast[c]
    colorlast[c]=e
  else:
    colorlast[c]=e


dp=[0]*(N+100)
dp[0]=1

for e,c in enumerate(clist,1):
  if poslp[e]==-1:
    dp[e]=(dp[e-1])%mod
  else:
    dp[e]=(dp[e-1]+dp[poslp[e]])%mod

# print(dp[:len(clist)+1])
print(dp[len(clist)]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,Q = map(int, input().split())
inf = float("inf")
S = [-inf] + [ int(input()) for _ in range(A)] + [inf]
T = [-inf] + [ int(input()) for _ in range(B)] + [inf]
# jinja = [-inf] + [ int(input()) for _ in range(A)] + [inf]
# tera = [-inf] + [ int(input()) for _ in range(B)] + [inf]
X = [ int(input()) for _ in range(Q)]

from bisect import bisect_left, bisect_right

# for i in range(Q):
#     q = X[i]
#     i = bisect_left(jinja, q)
#     j = bisect_left(tera, q)
#     left_jinja, right_jinja = q-jinja[i-1], jinja[i]-q
#     left_tera, right_tera = q-tera[j-1], tera[j]-q
#  
#     res = min(
#         max(left_jinja, left_tera),
#         left_jinja + right_tera + min(left_jinja, right_tera),
#         right_jinja + left_tera + min(right_jinja, left_tera),
#         max(right_jinja, right_tera)
#     )
#     print(res),
for q in range(Q):
    x = X[q]

    i = bisect_left(S, x)
    j = bisect_left(T, x)
    left_S , right_S =  x - S[i-1], S[i] - x
    left_T , right_T =  x - T[j-1], T[j] - x

    res = min( 
            max(left_S, left_T),
            left_S + right_T + min(left_S, right_T),
            right_S + left_T + min(right_S, left_T),
            max(right_S, right_T) 
            )
    print(res)



Fixed submission:
A,B,Q = map(int, input().split())
inf = float("inf")
import sys
input = sys.stdin.readline
S = [-inf] + [ int(input()) for _ in range(A)] + [inf]
T = [-inf] + [ int(input()) for _ in range(B)] + [inf]
X = [ int(input()) for _ in range(Q)]

from bisect import bisect_left, bisect_right

for q in range(Q):
    x = X[q]

    i = bisect_left(S, x)
    j = bisect_left(T, x)
    left_S , right_S =  x - S[i-1], S[i] - x
    left_T , right_T =  x - T[j-1], T[j] - x

    res = min( 
            max(left_S, left_T),
            left_S + right_T + min(left_S, right_T),
            right_S + left_T + min(right_S, left_T),
            max(right_S, right_T) 
            )
    print(res)
Buggy python submission (verdict: Runtime Error):
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


# mode = A[0] % 2
# B = []
# for a in A:
#     if a == 0:
#         mode = -1
#     elif a % 2 == mode:
#     elif a % 2 != mode:


fromEnd = []

i = 0
while i < L:
    if A[i] != 0:
        start = i
        while i < L and A[i] != 0:
            i += 1
        end = i-1 if i != start else start
        fromEnd.append((start, end, sum(A[start:end+1])))
    i += 1

ans = float("inf")

# start forward
mode = 2 % 2
sum_forward = sum(A)
for i in range(start, L):
    sum_forward = min(sum_forward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_forward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_forward -= A[i]

    elif A[i] == 0:
        sum_forward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_forward -= A[i]

    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_forward -= A[i] - 1
        mode = A[i] % 2 
    
    if i == L-1 and A[i] %2 == 0 and mode != A[i] %2:
        sum_forward -= 1

# print("sum forward: ", sum_forward)
ans = sum_forward
mode = 2 % 2
sum_backward = sum(A)


for i in range(end, -1, -1):
    ans = min(sum_backward, ans)
    
    # ans = min(sum_backward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_backward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_backward -= A[i]

    elif A[i] == 0:
        sum_backward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_backward -= A[i]
    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_backward -= A[i] - 1
        mode = A[i] % 2 
    if i == 0 and A[i] %2 == 0 and mode != A[i] %2:
        sum_backward -= 1

ans = min(sum_backward, sum_forward)
print(ans)

    


Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


DP = [0] * 5
for i in range(L):
    r0 = A[i]
    r1 = (A[i] + 1) % 2

    if A[i] == 0:
        r2 = 2
    else:
        r2 = A[i] % 2

    for i,r in zip(range(4,-1,-1), [r0,r2,r1,r2,r0]):
        DP[i] = min(DP[:i+1]) + r
        # print(DP)

print(min(DP))
Buggy python submission (verdict: Runtime Error):
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
ilist = [ tuple(zip(tuple(map(int, input().split())), ("a","b","c"))) for i in range(N)]

# print(ilist)
suml = [(0,"z")]
for i in range(1,N+1):
    l = (ilist[i-1])
    l = sorted(l, reverse=True)
    # print("list: ", l)
    if suml[i-1][1] != l[0][1]:
        # suml[i] = suml[i-1] + l[0][0]
        if (i+1)<=N and sorted(ilist[i+1], reverse=True)[0][1] == l[0][1]:
            # print("\tinside")
            l_n = sorted(ilist[i+1], reverse=True)# [0][1]
            if (l[0][0] + l_n[1][0]) < (l[1][0] + l_n[0][0]):

                suml.append(( suml[i-1][0]+l[1][0], l[1][1]  ))
            else:
                suml.append(( suml[i-1][0]+l[0][0], l[0][1]  ))
        else:
            suml.append(( suml[i-1][0]+l[0][0], l[0][1]  ))

        # // l[0][1] == sorted(ilist[i+1], reverse=True)[0][1]  \
        #  and l[0][0] + sorted(ilist[i+1], reverse=True)[0][1]
    else:
        # suml[i] = suml[i-1] + l[1][0]
        suml.append(( suml[i-1][0]+l[1][0], l[1][1]  ))

# print(suml)
print(suml[-1][0])





Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
# info = [ tuple(zip(tuple(map(int, input().split())), ("a","b","c"))) for i in range(N)]
info = [list(map(int, input().split())) for i in range(N)]
dp = [[0,0,0] for i in range(N+1)]
dp[1] = info[0]
for i in range(N):
    for j in range(3):
        for k in [x for x in range(3) if x != j]:
            if dp[i][k] + info[i][j] > dp[i+1][j]: # dp[i+1][j]?
                dp[i+1][j] = dp[i][k] + info[i][j]

# print(dp)
print(max(dp[N]))
Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
import numpy as np
N,W = list(map(int, input().split()))
wlist = [tuple(map(int, input().split())) for _ in range(N)]


# until ..w, v 
l = [(-1, 0, 0)]

ans = 0
while l:
    i_last, w, v = l.pop()
    if w > W:
        continue

    ans = max(ans, v)

    if i_last >= N-1:
        continue

    l.append( (i_last+1, w+wlist[i_last+1][0], 
                         v+wlist[i_last+1][1] ) )
    l.append( (i_last+1, w, 
                         v ) )
print(ans)

    



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM :  https://atcoder.jp/contests/dp/submissions/4127921

import numpy as np
N,W = list(map(int, input().split()))

wvlist = sorted( [ [int(x) for x in input().split()] for _ in range(N)] ) 

dp = [0] * (W+1)
cnt = 0
for w,v in wvlist:
    cnt = cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i] < dp[i-w]+v:
            dp[i] = dp[i-w] + v

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
import numpy as np
N,W = list(map(int, input().split()))
wlist = [tuple(map(int, input().split())) for _ in range(N)]
suml = [0 for _ in range(W+1)]

V = [[0 for _ in range(W+1)] for _ in range(N+1)]
for e,item in enumerate(wlist,1):
    w,v = item
    for wpoint in range(W+1):
        if w <= wpoint:
            V[e][wpoint] = max(V[e-1][wpoint -w] + v,
                     V[e][wpoint])
        else:
            V[e][wpoint] = V[e-1][wpoint]

# print(V)
print(np.array(V).max())



# # w, v
# for i in range(W+1):
#     for w,v in wlist:
#         if not (i+w) <= W:
#             continue
#         suml[i+w] = max(
#             suml[i+w],
#             suml[i] + v
#         )
#         print("\tsuml[{}+{}]: {}".format(i,w,suml[i+w]))
#         print("\tsuml[{}]:{} + v:{}".format(i, suml[i], v))
#     print(suml)
# print(max(suml))


Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM :  https://atcoder.jp/contests/dp/submissions/4127921

import numpy as np
N,W = list(map(int, input().split()))

wvlist = sorted( [ [int(x) for x in input().split()] for _ in range(N)] ) 

dp = [0] * (W+1)
cnt = 0
for w,v in wvlist:
    cnt = cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i] < dp[i-w]+v:
            dp[i] = dp[i-w] + v

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = map(int, input().split())
# *A = map(int, input().split())
A = list(map(int, input().split()))
dp = [ [0]*(K+1) for _ in range(N+1)]

dp[0][K]= 1
MOD= int(1e9+7)

for i in range(N): # i+1$B$K(B
    for k in range(K, -1, -1):

        for ai in range(A[i]+1): # ai = 0 to Ai
            if k - ai >= 0:
                dp[i+1][k-ai] += dp[i][k] % MOD
            # print("dp[{ip1}][{kai}] += dp[{i}][{k}]".format(ip1=i+1, kai=k-ai, i=i, k=k))
# print(dp[N][K])
print(dp[N][0] % MOD)
# print(dp)


Fixed submission:
from itertools import accumulate

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

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

MOD = int(1e9+7)

dp = [0] * (K+1)
dp[0] = 1

for n in range(N):

    sumlist = [0]
    sumlist += dp[:]
    sumlist = list(accumulate(sumlist))

    ndp = [0] * (K+1)
    for k in range(K+1):
        ndp[k] = sumlist[k+1] - sumlist[max(0, k - A[n])] 
        ndp[k] %= MOD
    dp = ndp
                # dp[k] ~ dp[k-A[n]] made
print(dp[K]%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))


Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))

Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = [ [int(j) for j in input().split()] for _ in range(N)]

dp = [ [0] * (1<<N) for _ in range(N+1)]
dp[0][0] = 1
MOD = int(1e9+7)

for S in range(1<<N):
    i = bin(S).count("1")
    for j in range(N):
        if not (1<<j) & S and A[i-1][j] == 1: # vacant lot
            dp[i+1][S^(1<<j)] += dp[i][S] % MOD

print(dp[N][(1<<N)-1] % MOD)


Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))

Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = [ [int(j) for j in input().split()] for _ in range(N)]

dp = [ [0] * (1<<N) for _ in range(N+1)]
dp[0][0] = 1
MOD = int(1e9+7)

for S in range(1<<N):
    i = bin(S).count("1")
    for j in range(N):
        if not (1<<j) & S and A[i-1][j] == 1: # vacant lot
            dp[i+1][S^(1<<j)] += dp[i][S] % MOD

print(dp[N][(1<<N)-1] % MOD)
            

            
    
    


Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))
Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
# ---------------------------------------------------------------------------------
from collections import deque
N0 = 2**(N).bit_length()
INF = float("inf")
INF = -(2**31-1) 

data = [INF]*(2*N0)

def update(k,x):
    k += N0 - 1
    data[k] = x
    # oldk = k
    # k += N0-1 # $B$3$N:n6H$O!D!D(B? #$B0lHV2<$NCJ$K(B
    # data[k] = k # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    # data[k] = oldk # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    while k >= 0:
        k = (k-1)//2
        data[k] = max(data[2*k+1], data[2*k+2])

# $B6h4V(B[l, r)$B$N:G>.CM(B
def query(l,r):
    L = l + N0 # $B$J$s$G(BN0$B$rB-$7$F$$$k!D(B?
    R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s,data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
# ---------------------------------------------------------------------------------
dp = [0] * (N+1)
#dp = [ [0] * (N+1) for _ in range(2*10**5+1)]

for i in range(1,N+1):
    dp[i] = max(query(0, H[i-1]), 0) + A[i-1]
    update(H[i-1], dp[i])
print(max(dp))



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
# ---------------------------------------------------------------------------------
from collections import deque
N0 = 2**(N).bit_length()
INF = float("inf")
INF = -(2**31-1) 

data = [INF]*(2*N0)

def update(k,x):
    k += N0 - 1
    data[k] = x
    # oldk = k
    # k += N0-1 # $B$3$N:n6H$O!D!D(B? #$B0lHV2<$NCJ$K(B
    # data[k] = k # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    # data[k] = oldk # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    while k >= 0:
        k = (k-1)//2
        data[k] = max(data[2*k+1], data[2*k+2])

# $B6h4V(B[l, r)$B$N:G>.CM(B
def query(l,r):
    L = l + N0 # $B$J$s$G(BN0$B$rB-$7$F$$$k!D(B?
    R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s,data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
# ---------------------------------------------------------------------------------
dp = [0] * (N+1)
#dp = [ [0] * (N+1) for _ in range(2*10**5+1)]

for i in range(1,N+1):
    dp[i] = max(query(0, H[i-1]), 0) + A[i-1]
    update(H[i-1], dp[i])
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
s = input()
s = s.replace('B', '1')
s = s.replace('W', '0')
s = list(s)

# print(s)
cnt = 0
def bsort(a):
    global cnt
    for i in range(len(a)-1):
        for j in range(i, len(a)):
            if int(a[j-1]) > int(a[j]):
                cnt += 1
                a[j-1] = '0'
                a[j] = '1'

bsort(s)
print(cnt)
            



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
s = input()
# s = s.replace('B', '1')
# s = s.replace('W', '0')
# s = list(s)
index = 0
sum = 0
for e,c in enumerate(s):
    if c == 'W':
        sum += e - index
        index += 1
        

        
# # print(s)
# cnt = 0
# def bsort(a):
#     global cnt
#     for i in range(len(a)-1):
#         for j in range(i, len(a)):
#             if int(a[j-1]) > int(a[j]):
#                 cnt += 1
#                 a[j-1] = '0'
#                 a[j] = '1'

# bsort(s)
print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))

dic = {}
for i in range(M):
    dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]
    dic[P[i]] = sorted(dic[P[i]])

# print(dic)
import numpy as np
for i in range(M):
    num = dic[P[i]].index(Y[i]) + 1
    # num = sorted(dic[P[i]]).index(Y[i]) + 1
    print("{0:06d}{1:06d}".format(P[i], num))

Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
yp = [(0,0,0)] * M
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))
    yp[i] = (Y[i], P[i], i)

yp.sort()
dic = {}
# for i in range(M):
#     dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]
#     dic[P[i]] = sorted(dic[P[i]])

# print(yp)
pre = [0] * (N+1)
ansnum = [0] * M
for (y,p,i) in yp:
    pre[p] += 1
    ansnum[i] = "{0:06d}{1:06d}".format(p, pre[p])

import numpy as np
for i in range(M):
    print(ansnum[i])
    # num = yp[]
    # num = dic[P[i]].index(Y[i]) + 1
    # print("{0:06d}{1:06d}".format(P[i], num))

Buggy python submission (verdict: Time Limit Exceeded):
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))

dic = {}
for i in range(M):
    dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]

# print(dic)
import numpy as np
for i in range(M):
    num = sorted(dic[P[i]]).index(Y[i]) + 1
    print("{0:06d}{1:06d}".format(P[i], num))

Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
yp = [(0,0,0)] * M
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))
    yp[i] = (Y[i], P[i], i)

yp.sort()
dic = {}
# for i in range(M):
#     dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]
#     dic[P[i]] = sorted(dic[P[i]])

# print(yp)
pre = [0] * (N+1)
ansnum = [0] * M
for (y,p,i) in yp:
    pre[p] += 1
    ansnum[i] = "{0:06d}{1:06d}".format(p, pre[p])

import numpy as np
for i in range(M):
    print(ansnum[i])
    # num = yp[]
    # num = dic[P[i]].index(Y[i]) + 1
    # print("{0:06d}{1:06d}".format(P[i], num))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
S=input()
T=input()
ans=["-1"]*()
def computeGCD(x, y): 
  if x > y: 
    small = y    
  else: 
    small = x
  for i in range(1, small+1): 
    if((x % i == 0) and (y % i == 0)): 
      gcd = i 
  return gcd 

lena=computeGCD(N,M)
glena=N*M//lena#45 , 15,9 , 3,5 
comm=computeGCD(glena//N, glena//M)
gcomm=(glena//N)*(glena//M)//comm
for i in range(glena//gcomm):
  if S[i*glena//M]!=T[i*glena//N]:
    print(-1)
    exit()
print(glena)

Fixed submission:
N,M = map(int, input().split())
S = input()
T = input()
from fractions import gcd

# 15, 9
# 3$BJ8;z$:$D8+$F$$$/!"(B5$BJ8;z$:$D8+$F$$$/(B
LEN = N*M // gcd(N,M) # 45
p = LEN // N # 3
q = LEN // M # 5
lcm = p*q//gcd(p,q)

for i in range(0, LEN//lcm):
    if S[i*q] != T[i*p]:
        print(-1)
        exit()
print(LEN)
Buggy python submission (verdict: Runtime Error):
#!/mnt/c/Users/moiki/bash/env/bin/python
import math
from functools import reduce


N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]

print( reduce(math.gcd, A) )



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# import math
from functools import reduce
def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]

print( reduce(gcd, A) )

Buggy python submission (verdict: Runtime Error):
#!/mnt/c/Users/moiki/bash/env/bin/python
N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]
import math
from functools import reduce

print( reduce(math.gcd, A) )



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# import math
from functools import reduce
def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]

print( reduce(gcd, A) )

Buggy python submission (verdict: Runtime Error):
#!/mnt/c/Users/moiki/bash/env/bin/python
N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]
import math
from functools import reduce

print( reduce(math.gcd, A) )



Fixed submission:
#!/mnt/c/Users/moiki/bash/env/bin/python
# import math
from functools import reduce
def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]

print( reduce(gcd, A) )