Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())

#桁DP
string = str(N)
digits = len(string)

#dp[i][j][k]=と同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
#k=0: i桁目まで見てN未満が確定, k=1: 未確定
dp = [[[0]*2 for _ in range(K+1)] for __ in range(digits+1)]
#初期状態
dp1[0][0][1] = 1

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nk = 1 if k == 1 and nd == d else 0
                if k == 1 and nd > d: break

                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue

                dp[ni][nj][nk] += dp[i][j][k]

print(dp[digits][K][0] + dp[digits][K][1])


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

sN=str(N)
keta=len(sN)

#dp[i][j][t]=Nと同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(1,keta+1):
    for j in range(K+1):
        if sN[i-1]=='0':
            dp[i][j][1] = dp[i-1][j][1]
        elif j>0:
            dp[i][j][1] = dp[i-1][j-1][1]
        dp[i][j][0] = dp[i-1][j][0]
        if sN[i-1]!='0':
            dp[i][j][0] += dp[i-1][j][1]
        if j>0:
            dp[i][j][0] += dp[i-1][j-1][1]*(max(0,int(sN[i-1])-1))
            dp[i][j][0] += dp[i-1][j-1][0]*9

print(dp[keta][K][0]+dp[keta][K][1])
Buggy python submission (verdict: Runtime Error):
r1,c1,r2,c2=map(int, input().split())
MOD=10**9+7

M=10**6
fac=[0]*(M+1)
ifac=[0]*(M+1)
fac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%MOD
ifac[M]=pow(fac[M],MOD-2,MOD)
for i in range(M-1,0,-1):
    ifac[i]=ifac[i+1]*(i+1)%MOD

def comb(a,b): return fac[a]*ifac[a-b]*ifac[b]%MOD

def g(r,c): return comb(r+c+2,r+1)-1

ans=g(r2,c2)-g(r1-1,c2)-g(r2,c1-1)+g(r1-1,c1-1)
print(ans%MOD)

Fixed submission:
r1,c1,r2,c2=map(int, input().split())
MOD=10**9+7

M=2*(10**6+1)
fac=[0]*(M+1)
ifac=[0]*(M+1)
fac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%MOD
ifac[M]=pow(fac[M],MOD-2,MOD)
for i in range(M-1,0,-1):
    ifac[i]=ifac[i+1]*(i+1)%MOD

def comb(a,b): return fac[a]*ifac[a-b]*ifac[b]%MOD

def g(r,c): return comb(r+c+2,r+1)-1

ans=g(r2,c2)-g(r1-1,c2)-g(r2,c1-1)+g(r1-1,c1-1)
print(ans%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
H,N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

INF=10**9

dp=[INF for _ in range(H+1)]
dp[H]=0
for h in range(H,0,-1):
    for n in range(N):
        A,B=AB[n]
        newH=max(0,h-A)
        dp[newH]=min(dp[newH], dp[h]+B)

print(dp[0])

Fixed submission:
H,N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

INF=10**9

dp=[INF for _ in range(H+1)]
dp[H]=0
for h in range(H,0,-1):
    for n in range(N):
        A,B=AB[n]
        newH=max(0,h-A)
        dp[newH]=min(dp[newH], dp[h]+B)

print(dp[0])
Buggy python submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    str_N = str(N)
    head_N, tail_N = int(str_N[0]), int(str_N[-1])
    digits = len(str_N)
    m = int(str_N[1:-1])
        
    def f(x):
        s = str(x)
        head, tail = int(s[0]), int(s[-1])
        res = 0
        if head == tail: res += 1 #1桁
        if digits >= 2: #2桁
            if digits == 2:
                if tail <= head_N: res += 1
            else: res += 1
        for d in range(3, digits+1): #3桁以上
            k = d - 2
            if d == digits: #Nと同じ桁数
                if tail < head_N:
                    res += 10**k
                elif tail == head_N:
                    res += m
            else: res += 10**k

        return res

    ans = 0
    for n in range(1,N+1):
        if n % 10 == 0: continue
        ans += f(n)
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
N=int(input())

def cnt(i,j):
    ret=0
    si=str(i)
    for n in range(1,N+1):
        if n%10!=j:
            continue
        if str(n)[0]!=si:
            continue
        ret+=1
    return ret

ans=0
for i in range(10):
    for j in range(10):
        ans+=cnt(i,j)*cnt(j,i)
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque
from collections import Counter
N=int(input())
E=[set() for _ in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    E[a].add((b,i))
    E[b].add((a,i))
M=int(input())
P=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

pc=[set() for _ in range(M)] #各制約で使用する辺の集合

def bfs(S,G,p):
    q=deque([S])
    parent=[(-1,-1)]*N
    while q:
        n=q.popleft()
        for to,i in E[n]:
            if parent[to][0]!=-1:
                continue
            parent[to]=(n,i)
            if to==G:
                break
            q.append(to)
    n=G
    while n!=S:
        n,i=parent[n]
        pc[p].add(i)

for i,p in enumerate(P):
    bfs(p[0],p[1],i)

ans=0
for i in range(1<<M):
    whiteset=set()
    sign=1
    for j in range(M):
        if i>>j&1:
            whiteset|=pc[j]
            sign*=-1
    ans+=sign*(1<<(N-1-len(whiteset)))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

def judge(L):
    for i in range(N-1):
        if L[i]>L[i+1]:
            return False
    return True

def swap(LA,LB,i):
    LA[i],LB[i+1]=LB[i+1],LA[i]
    LA[i+1],LB[i]=LB[i],LA[i+1]

def hash(LA,LB):
    v=0
    for a in LA:
        v+=a
        v*=51
    for b in LB:
        v+=b
        v*=51
    return v

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

Q=deque()
for i in range(N-1):
    Q.append((0,i,A[:],B[:]))
ans=0
V=set()
while Q:
    d,i,LA,LB=Q.popleft()
    if i>18:
        print(-1)
        exit()
    swap(LA,LB,i)
    h=hash(LA,LB)
    if h in V:
        continue
    if judge(LA):
        print(d+1)
        exit()
    V.add(h)
    for i in range(N-1):
        Q.append((d+1,i,LA[:],LB[:]))
print(-1)
exit()


Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

#0-indexed

#カードiが左からjの位置にあるときの表の数字
def getNum(i,j):
    return B[i] if abs(i-j)&1 else A[i]

#dp[使用済みカードを表すbit列][いちばん右のカードNo]=最小操作回数
INF=10**9
dp=[[INF for _ in range(N)] for __ in range(1<<N)]
for i in range(N):
    dp[1<<i][i] = i

for m in range(1,1<<N): #配置済みカードパターン
    cnt=bin(m).count('1') #配置済みカード数
    idx=dict() #未配置カードの位置
    tmp=cnt
    for i in range(N):
        if m & (1<<i) == 0:
            idx[i]=tmp
            tmp+=1
    for j in range(N): #新たに並べるカード
        if m & (1<<j):
            #もう使ったやつです
            continue
        num_j=getNum(j,cnt)
        for i in range(N): #配置済みのいちばん右にあるカード
            if m & (1<<i) == 0:
                #まだ配置済みじゃないです
                continue
            num_i=getNum(i,cnt-1)
            if num_i>num_j:
                #単調増加になりません
                continue
            dp[m|(1<<j)][j] = min(dp[m|(1<<j)][j], dp[m][i] + idx[j]-cnt)

ans=INF
for i in range(N):
    ans=min(ans,dp[(1<<N)-1][i])
print(ans if ans<INF else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

for k in range(N):
    x=A[(k)%N]^B[0]
    for i in range(1,N):
        if x!=A[(i+k)%N]^B[i]:
            break
    else:
        print(k,x)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

AX=[A[i%N]^A[(i-1)%N] for i in range(N,0,-1)]
BX=[B[i%N]^B[(i-1)%N] for i in range(N,0,-1)]
BX2=BX+BX
#print(BX2)
#print(AX)

shift=[0]*(N+1)
k=1
l=0
while k<N:
    if AX[k]==AX[l]:
        k+=1
        l+=1
        shift[k]=l
    elif l>0:
        l=shift[l]
    else:
        k+=1
        shift[k]=0
#print(shift)

ans=[]
ai=bi=0
Z=0
while bi<N:
    #print(bi,ai)
    if BX2[bi+ai]==AX[ai]:
        ai+=1
        if ai==N-1:
            print(bi,A[bi]^B[0])
            ans.append((bi+1)%N)
            bi+=ai-shift[ai]
            ai=shift[ai]
    else:
        bi+=1 if ai==0 else ai-shift[ai]
        ai=shift[ai]
Buggy python submission (verdict: Time Limit Exceeded):
N,M,V,P=map(int, input().split())
*A,=map(int, input().split())

A.sort()
ans=P
for i in range(N-P):
    Ax = A[-P]  #上位Pの中の最下位
    mine = A[i] + M #自分に全力で投票
    if mine < Ax: continue #逆転不能
    votes = M*V
    votes -= M #自分への票
    votes -= min(P-1, V) * M #上位陣のx以外に全力で投票
    votes -= sum([min(mine - A[j], M) for j in range(N-P+1) if i!=j]) #逆転されない程度に下位陣に投票
    if votes > 0 : continue #再逆転される
    ans += 1
print(ans)

Fixed submission:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
p = A[P-1]

#X番目の問題に可能性があるかどうか(0-indexed)
def f(X):
    x = A[X]
    if x + M < p: return False
    votes = M*V
    votes -= M * (P-1)
    for i in range(P-1,N):
        votes -= min(M, x + M - A[i])
    return votes <= 0

ok = 0
over = N
while over - ok > 1:
    mid = (over + ok) // 2
    if f(mid): ok = mid
    else: over = mid
print(ok+1)
Buggy python submission (verdict: Runtime Error):
import queue
N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
used = [False]*N
def dfs(i,end):
    global r
    used[i] = True
    if i==end:
        r.append(i)
        return True
    for e in E[i]:
        if not used[e]:
            if dfs(e,end):
                r.append(i)
                return True
    return False
dfs(v,u)

ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
used = [False]*N
def dfs2(i,end,d):
    global dmax
    used[i] = True
    if i==end:
        return
    dmax = max(dmax,d)
    for e in E[i]:
        if not used[e]:
            dfs2(e,end,d+1)
dfs2(u,v,0)
ans += dmax - 1

print(ans)

Fixed submission:
N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
parent = [-1]*N
def dfs(root,end):
    global r
    stack = []
    stack.append(root)
    parent[root] = root
    while len(stack)>0:
        p = stack.pop()
        if p==end:
            break
        for e in E[p]:
            if parent[e]==-1:
                parent[e] = p
                stack.append(e)
    p=end
    while p!=root:
        r.append(p)
        p = parent[p]
    r.append(root)

dfs(v,u)
ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
depth = [-1]*N
def dfs2(root,end,d):
    global dmax
    stack = []
    stack.append(root)
    depth[root] = d
    depth[end] = 0
    while len(stack)>0:
        p = stack.pop()
        for e in E[p]:
            if depth[e]==-1:
                depth[e] = depth[p]+1
                dmax = max(dmax,depth[e])
                stack.append(e)

dfs2(u,v,0)
ans += dmax - 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
xy=[[] for in range(N)]
for _ in range(N):
    A = int(input())
    for __ in range(A):
        x, y = map(int, input().split())
        xy[_].append((x-1,y))

ans = 0
for p in range(1<<N):
    h = []
    judge = True
    for i in range(N):
        h.append(p&1)
        p>>=1
    for i in range(N):
        for x, y in xy[i]:
            if h[i] and y != h[x]:
                judge = False
                break
        if not judge: break
    if not judge: continue
    ans = max(ans,sum(h))

print(ans)


Fixed submission:
N = int(input())
A = []
for _ in range(N):
    a = int(input())
    xy = []
    for __ in range(a):
        xy.append(tuple(map(int,input().split())))
    A.append(xy)

ok = []
for i in range(2**N):
    v = [0] * (N+1)
    n = i
    for j in range(1, N+1):
        v[j] = n % 2
        n >>= 1
    for k, xys in enumerate(A):
        if v[k+1] == 1:
            for xy in xys:
                if xy[1] != v[xy[0]]:
                    break
            else:
                continue
            break
    else:
        ok.append(v)

ans = 0
for a in ok:
    ans = max(ans,sum(a))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n**(j-1) % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)


Fixed submission:
import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)

Buggy python submission (verdict: Time Limit Exceeded):
import fractions

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = set()
i = 1
while i * i <= gcd:
    if gcd % i == 0:
        cd.add(i)
        cd.add(gcd//i)
    i += 1

ans = set()
for n in sorted(cd):
    if n == 1:
        continue
    for j in ans:
        if n**(j-1) % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)


Fixed submission:
import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
A = deque(A)
for i in range(M):
    A[N-1] //= 2
    if N >=2 and A[N-1] > A[N-2]:
        continue
    p = A.pop()
    index = bisect.bisect_left(A, p)
    A.insert(index, p)
print(sum(A))

Fixed submission:
import heapq
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [(-x, x) for x in A]
heapq.heapify(A)
for i in range(M):
    P = heapq.heappop(A)
    p = P[1] // 2
    heapq.heappush(A, (-p, p))
s = 0
for i in range(N):
    s += A[i][1]
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(M):
    p = A.pop()
    p //= 2
    index = bisect.bisect_left(A, p)
    A.insert(index, p)
print(sum(A))

Fixed submission:
import heapq
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [(-x, x) for x in A]
heapq.heapify(A)
for i in range(M):
    P = heapq.heappop(A)
    p = P[1] // 2
    heapq.heappush(A, (-p, p))
s = 0
for i in range(N):
    s += A[i][1]
print(s)
Buggy python submission (verdict: Runtime Error):
N=input()
print(N*N*N)

Fixed submission:
N = int(input())
print(N**3)
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    d = 0
    while True:
        c = [False] * N
        for i in range(N):
            if idx[i] >= N - 1: continue
            if c[i]: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                c[i] = True
                c[m] = True
        f = False
        for i in range(N):
            if c[i]:
                idx[i] += 1
                f = True
        if not f:
            print(-1)
            return
        d += 1
        if all([idx[i] >= N - 1 for i in range(N)]):
            print(d)
            return

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)


Fixed submission:
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

indices = [0] * N
def next(i):
    return A[i][indices[i]] if indices[i] < N-1 else -1

from collections import deque
q = deque()
for i in range(N):
    j = next(i)
    if i < j and next(j) == i:
        q.append((i, j))

m = N*(N-1)//2
days = 0
while q:
    days += 1
    nq = deque()
    while q:
        i, j = q.pop()
        m -= 1
        indices[i] += 1
        indices[j] += 1
        ni = next(i)
        nj = next(j)
        if ni >= 0 and next(ni) == i:
            nq.append((i, ni))
        if nj >= 0 and nj != i and next(nj) == j:
            nq.append((j, nj))
    q = nq

if m > 0:
    print(-1)
else:
    print(days)
Buggy python submission (verdict: Runtime Error):
S = input()

def divide_str_to_list(s, before):
    for i in range(1, len(s)):
        if s[0:i] != before and s[i:] != s[0:i]:
            return 1 + divide_str_to_list(s[i:], s[0:i])
    return 1

print(divide_str_to_list(S, ""))


Fixed submission:
S = input()
before = ""

count = 0
i = 0
while i < len(S):
    for l in range(1, len(S) - i):
       if S[i:i+l] != before and S[i:i+l] != S[i+l:]:
           count += 1
           before = S[i:i+l]
           break
    i += l

print(count+1)

Buggy python submission (verdict: Runtime Error):
S = input()

def divide_str_to_list(s, before):
    for i in range(1, len(s)):
        if s[0:i] != before and s[i:] != s[0:i]:
            return [s[0:i]] + divide_str_to_list(s[i:], s[0:i])
    return [s]

print(len(divide_str_to_list(S, "")))


Fixed submission:
S = input()
before = ""

count = 0
i = 0
while i < len(S):
    for l in range(1, len(S) - i):
       if S[i:i+l] != before and S[i:i+l] != S[i+l:]:
           count += 1
           before = S[i:i+l]
           break
    i += l

print(count+1)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
S = [input() for i in range(N)]

for i, s in enumerate(S):
    S[i] = "".join(sorted(list(s)))

skiptbl = [False for j in range(N)]
count = 0
for i in range(N):
    if skiptbl[i]:
        continue
    d = 0
    for j in range(i+1, N):
        if skiptbl[j]:
            continue
        if S[i] == S[j]:
            d += 1
            skiptbl[j] = True
    count += d if d <= 1 else d + math.factorial(d) / (2 * math.factorial(d - 2))
print(int(count))


Fixed submission:
N = int(input())
S = [input() for i in range(N)]

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))

Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
S = [input() for i in range(N)]
count = 0
l = [False for i in range(N)]
for i, s in enumerate(S):
    if l[i]:
        continue
    sset = set(s)
    d = 0
    for j in range(i+1, N):
        if l[j]:
            continue
        for c in sset:
            if s.count(c) != S[j].count(c):
                break
        else:
            d += 1
            l[j] = True
    count += d if d <= 1 else d + math.factorial(d) / (2 * math.factorial(d - 2))
print(int(count))


Fixed submission:
N = int(input())
S = [input() for i in range(N)]

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]
count = 0
for i, s in enumerate(S):
    for j in range(i+1, N):
        for c in s:
            if s.count(c) != S[j].count(c):
                break
        else:
            count += 1
print(count)


Fixed submission:
N = int(input())
S = [input() for i in range(N)]

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[1], reverse=True)
for day in reversed(range(M)):
    for i, ab in enumerate(AB):
        if ab[0] + day <= M:
            earn += ab[1]
            del AB[i]
            break
print(earn)


Fixed submission:
import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[0])
pos=0
cando=[]
for remain in range(M+1):
    for i in range(pos,len(AB)):
        if AB[i][0] <= remain:
            heapq.heappush(cando, -AB[i][1])
            pos=i+1
        else:
            pos=i
            break
    if cando:
        earn-=heapq.heappop(cando)
print(earn)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

earn = 0
for day in reversed(range(M)):
    maxearn = -1
    maxindex = -1
    for i, ab in enumerate(AB):
        if ab[0] + day <= M:
            if ab[1] > maxearn:
                maxearn = ab[1]
                maxindex = i
    if maxindex == -1:
        continue
    earn += maxearn
    del AB[maxindex]

print(earn)


Fixed submission:
import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[0])
pos=0
cando=[]
for remain in range(M+1):
    for i in range(pos,len(AB)):
        if AB[i][0] <= remain:
            heapq.heappush(cando, -AB[i][1])
            pos=i+1
        else:
            pos=i
            break
    if cando:
        earn-=heapq.heappop(cando)
print(earn)