Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7

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

p, m = [], []
zero = False
for x in a:
    if x == 0:
        zero = True
        continue
    elif x >= 0: p.append(x)
    else: m.append(x)

if len(p) == 0 and len(m) == 0:
    print(0)
    exit()

p.sort(reverse=True)
m.sort()
mr = list(reversed(m))

def cum(s):
    n = len(s)
    cs = [1] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] * s[i]
    return cs

pc = cum(p)
mc = cum(m)
mrc = cum(mr)

ans = -float("inf")
pl, ml = len(p), len(m)

d = min(pl, k)

for pn in range(d+1)[::-1]:
    mn = k - pn
    if mn > ml: continue
    tmp = pc[pn] * mc[mn]
    tmp1 = pc[pn] * mrc[mn]

    ans = max(ans, tmp, tmp1)

if ans < 0 and zero:
    print(0)
else: 
    print(ans % MOD)


Fixed submission:
MOD = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
p, q = [], []
for x in a:
    if x >= 0: p.append(x)
    else: q.append(x)
lp, lq = len(p), len(q)

def sp():
    p.sort(reverse=True)
    q.sort()
    ans = p[0] if k % 2 else 1
    s = []
    for i in range(0, lq-1, 2):
        s.append(q[i]*q[i+1])
    for i in range(k % 2, lp-1, 2):
        s.append(p[i]*p[i+1])
    s.sort(reverse=True)
    for i in range(k//2):
        ans *= s[i]
        ans %= MOD
    print(ans)

def sq():
    a.sort(key=lambda x: abs(x))
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= MOD
    print(ans)

if k % 2 and not p: sq()
elif n == k and lq % 2: sq()
else: sp()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
s = 0
for x in a: s ^= x

ans = [0] * n
for i in range(n):
    res = 0
    x, y = a[i], s
    for j in range(50):
        if x % 2 != y % 2: res += 2**j
        x >>= 1
        y >>= 1
    ans[i] = res

print(*ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
s = 0
for x in a: s ^= x

ans = [0] * n
for i in range(n):
    res = 0
    x, y = a[i], s
    for j in range(50):
        if x % 2 != y % 2: res += 2**j
        x >>= 1
        y >>= 1
    ans[i] = res

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
a.sort()

m = 10**6+10
d = [False] * (m+1)
ans = 0
for i in range(n):
    same = (i > 0 and a[i] == a[i-1]) or (i < (n-1) and a[i] == a[i+1])
    x = a[i]
    if not d[x] and not same: ans += 1
    for j in range(x, m+1, x):
        d[j] = True
    
print(ans)


Fixed submission:
import sys
input = lambda: sys.stdin.buffer.readline()

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

m = 10**6+10
d = [False] * (m+1)
ans = 0
for i in range(n):
    same = (i > 0 and a[i] == a[i-1]) or (i < (n-1) and a[i] == a[i+1])
    x = a[i]
    if not d[x] and not same: ans += 1
    
    if (i > 0 and a[i] == a[i-1]): continue
    for j in range(x, m+1, x):
        d[j] = True
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, w, K = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

print(ans)


Fixed submission:
h, w, K = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

print(ans)
Buggy python submission (verdict: Runtime Error):
n, p = map(int, input().split())
s = list(map(int, input()))
ans = 0

if p == 2 or p == 5:
    for i, x in enumerate(s):
        if (p == 2 and not x % 2) or (p == 5 and (x == 0 or x == 5)):
            ans += i+1
    print(ans)
    exit()

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * 10
for x in cum: t[x] += 1

for x in t:
    ans += x * (x-1) // 2
print(ans)


Fixed submission:
n, p = map(int, input().split())
s = list(map(int, input()))
ans = 0

if p == 2 or p == 5:
    for i, x in enumerate(s):
        if (p == 2 and not x % 2) or (p == 5 and (x == 0 or x == 5)):
            ans += i+1
    print(ans)
    exit()

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum: t[x] += 1

for x in t:
    ans += x * (x-1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp = [[0] * 2 for _ in range(n)]
dp[-1][0], dp[-1][1] = 1, 1

for i in range(n-1)[::-1]:
    dp[i][0] = dp[i+1][0] + dp[i+1][1] % MOD
    dp[i][1] = dp[s.get(i)][0]

print(sum(dp[0]) % MOD)


Fixed submission:
import sys
from bisect import bisect_left, bisect_right
input = lambda: sys.stdin.readline()
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp1, dp2 = [0] * n, [0] * n
dp1[-1], dp2[-1] = 1, 1

for i in range(n-1)[::-1]:
    dp1[i] = dp1[i+1] + dp2[i+1] % MOD
    dp2[i] = dp1[s.get(i)]

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

def init_mod_c(lim=10**6*2, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)

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

def init_mod_c(lim=10**7, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7

def init_mod_c(lim=10**6*2, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)


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

def init_mod_c(lim=10**7, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = sum(d) * s % MOD

for i in range(m):
    p = 1
    for j in range(i+1, n-1):
        c = j - i
        p *= c * inv[c+1]
        p %= MOD
        ans += d[j] * p * s
        ans %= MOD

print(ans)


Fixed submission:
MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = s * sum(d) % MOD

p = 0
for i in range(1, m):
    p += inv[i+1]
    p %= MOD
    ans += s * d[i] * p
    ans %= MOD

print(ans)

Buggy python submission (verdict: Runtime Error):
MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

s = 1
for i in range(2, n):
    s *= i
ans = sum(d) * s % MOD

for i in range(m):
    p = 1
    for j in range(i+1, n-1):
        c = j - i
        p *= c / (c+1)
        ans += d[j] * int(p * s)
        ans %= MOD

print(int(ans))


Fixed submission:
MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = s * sum(d) % MOD

p = 0
for i in range(1, m):
    p += inv[i+1]
    p %= MOD
    ans += s * d[i] * p
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = 2**(n-1), 0 if n <= 1 else 2**(n-2)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * (2 ** n % MOD) % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = 2**(n-1), 0 if n <= 1 else 2**(n-2)
for i, x in enumerate(c):
    cnt += (a + b*i) * x

print(cnt * (2 ** n % MOD) % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
pt = [2**i for i in range(n+1)]

for i, x in enumerate(c):
    r = n-i-1
    cnt += (pt[i] + (0 if i <= 0 else pt[i-1]) * i) * pt[r] * x
    cnt %= MOD

print(cnt * (pt[n] % MOD) % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0

for i, x in enumerate(c):
    r = n-i-1
    cnt += (2**i + int(2**(i-1)) * i) * (2**r) * x
    cnt %= MOD

print(cnt * (2**n % MOD) % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n = int(input())
s = list(input())

dp = np.zeros((n+1, n+1), dtype=np.int64)
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]: dp[i][j] = dp[i+1][j+1] + 1
        ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)


Fixed submission:
n = int(input())
s = input()

dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
             dp[i][j] = dp[i+1][j+1] + 1
             ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(input())

dp = [[0 for _ in range(5001)]] * 5001
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
            a = dp[i+1][j+1]
            dp[i][j] = a + 1
        ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)


Fixed submission:
n = int(input())
s = input()

dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
             dp[i][j] = dp[i+1][j+1] + 1
             ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = [(int(x), i) for i, x in enumerate(input().split())]
p.sort(reverse=True)

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (self.n+1)
    
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def add(self, i, x):
        if i <= 0: return
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def lower_bound(self, x):
        if x <= 0: return 0
        cur, s, k = 0, 0, 1 << (self.n.bit_length()-1)
        while k:
            nxt = cur + k 
            if nxt <= self.n and s + self.data[nxt] < x:
                s += self.data[nxt]
                cur = nxt
            k >>= 1
        return cur + 1

bit = BinaryIndexedTree(n)
ans = 0

for x, i in p:
    i += 1
    bit.add(i, 1)
    idx = bit.sum(i)
    l1, l2 = bit.lower_bound(idx-1), bit.lower_bound(idx-2)
    r1, r2 = bit.lower_bound(idx+1), bit.lower_bound(idx+2)
    ans += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * x

print(ans)


Fixed submission:
n = int(input())
p = [(int(x), i) for i, x in enumerate(input().split())]
p.sort(reverse=True)

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (self.n+1)
    
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def add(self, i, x):
        if i <= 0: return
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def lower_bound(self, x):
        if x <= 0: return 0
        cur, s, k = 0, 0, 1 << (self.n.bit_length()-1)
        while k:
            nxt = cur + k 
            if nxt <= self.n and s + self.data[nxt] < x:
                s += self.data[nxt]
                cur = nxt
            k >>= 1
        return cur + 1

bit = BinaryIndexedTree(n)
ans = 0

for x, i in p:
    i += 1
    bit.add(i, 1)
    idx = bit.sum(i)
    l1, l2 = bit.lower_bound(idx-1), bit.lower_bound(idx-2)
    r1, r2 = bit.lower_bound(idx+1), bit.lower_bound(idx+2)
    ans += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * x

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
d = defaultdict(list)

for i, x in enumerate(s):
    for j in range(len(t)):
        d[x].append(i + len(s) * j)
for x in d.values(): x.sort()

ans = 0
for x in t:
    if x not in d: print(-1); exit()
    ans = d[x][bisect_right(d[x], ans)]

print(ans+1)


Fixed submission:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
idxs = defaultdict(list)

for i, c in enumerate(s):
    idxs[c].append(i)
for i, c in enumerate(s):
    idxs[c].append(len(s) + i)

ans, cur_i = -1, -1
for c in t:
    if c not in idxs: print(-1); break
    a = idxs[c]
    nxt = a[bisect_right(a, cur_i)]
    ans += nxt - cur_i
    cur_i = nxt % len(s)
else: print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = []

for _ in range(n):
    w = list(input())
    w.sort()
    s.append("".join(w))

count = 0

for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            count += 1

print(count)


Fixed submission:
import collections

n = int(input())
s = []


def main():
    for _ in range(n):
        w = list(input())
        w.sort()
        s.append("".join(w))

    counter = collections.Counter(s)
    _, c = zip(*counter.most_common())

    ans = 0

    for num in c:
        if num == 1:
            return ans
        ans += num * (num-1) // 2

    return ans


print(main())
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

n, m = map(int, input().split())

abl = []


def main():
    for i in range(n):
        abl.append(tuple(map(int, input().split())))

    abl.sort()

    ans = 0
    q = []

    for i in range(1, m+1):
        for j, ab in enumerate(abl):
            if ab[0] == i:
                heappush(q, -ab[1])
        if q:
            ans += -heappop(q)

    return ans


print(main())


Fixed submission:
from heapq import heappush, heappop

n, m = map(int, input().split())

abl = []
for i in range(n):
    abl.append(tuple(map(int, input().split())))
abl.sort()

q = []
count = 0
ans = 0

for i in range(1, m+1):
    while count < n:
        a, b = abl[count]
        if a > i:
            break
        heappush(q, -b)
        count += 1
    if q:
        ans += -heappop(q)

print(ans)

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

abl = []


def main():
    for i in range(n):
        abl.append(tuple(map(int, input().split())))

    abl.sort()

    ans = 0

    for i in range(1, m+1):
        bm, mi = -1, -1

        for j, ab in enumerate(abl):
            if ab[0] > i:
                break
            if ab[1] > bm:
                bm = ab[1]
                mi = j

        if bm >= 0 and mi >= 0:
            ans += bm
            del abl[mi]

    return ans


print(main())


Fixed submission:
from heapq import heappush, heappop

n, m = map(int, input().split())

abl = []
for i in range(n):
    abl.append(tuple(map(int, input().split())))
abl.sort()

q = []
count = 0
ans = 0

for i in range(1, m+1):
    while count < n:
        a, b = abl[count]
        if a > i:
            break
        heappush(q, -b)
        count += 1
    if q:
        ans += -heappop(q)

print(ans)