Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
x, y = map(int, input.split())
print(x + y // 2)

Fixed submission:
x, y =map(int, input().split())
print(x + y // 2)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
pys = [[] for _ in range(n + 1)]

ans = [None for _ in range(m)]

for i in range(m):
    p, y = map(int, input().split())
    lst = [y, i]
    pys[p].append(lst)

for p in range(1, n + 1):
    t = sorted(pys[p], key=lambda x: x[0])
    for j, [y, i] in enumerate(t, 1):
        ans[i] = f'{p:06}{j:06}'

print('\n'.join(ans))

'''
zero padding: 
f'{i:03}'
002etc
'''

Fixed submission:
from bisect import bisect_left

n, m = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(m)]
pys = [[] for _ in range(n)]
for q in qs:
    p, y = q
    p -= 1
    pys[p].append(y)

for i in range(n):
    pys[i] = sorted(pys[i])

for q in qs:
    p, y = q
    p -= 1
    number = bisect_left(pys[p], y) + 1

    print(str(p + 1).zfill(6) + str(number).zfill(6))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
d = [[] for _ in range(n)]
for py in pys:
    p, y = py
    d[p - 1].append(y)

for i in range(n):
    d[i] = sorted(d[i])

for py in pys:
    p, y = py
    number = d[p - 1].index(y) + 1

    print(str(p).zfill(6) + str(number).zfill(6))

Fixed submission:
from bisect import bisect_left

n, m = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(m)]
pys = [[] for _ in range(n)]
for q in qs:
    p, y = q
    p -= 1
    pys[p].append(y)

for i in range(n):
    pys[i] = sorted(pys[i])

for q in qs:
    p, y = q
    p -= 1
    number = bisect_left(pys[p], y) + 1

    print(str(p + 1).zfill(6) + str(number).zfill(6))
Buggy python submission (verdict: Runtime Error):
def main():
    from collections import deque
    from decimal import Decimal, getcontext

    getcontext().prec = 1000

    N = int(input())

    # {1,...,N}*2を分割
    # k個の集合があって
    # 各集合は他のk-1個の集合に対し共通要素を1個ずつ合わせてk-1個の要素をもつ

    sq = Decimal(N * 8 + 1).sqrt()
    cond = sq % 2 == 1  # 奇数か

    if not cond:
        print('No')
        return
    k = int((1 + sq) // 2)  # Decimalのままだとrangeの引数に使えない
    print('Yes')
    print(k)

    deqs = []
    it = iter(range(1, N + 1))
    for _ in range(k):
        print(k - 1, end=' ')
        t = []
        for deq in deqs:
            x = deq.popleft()
            t.append(x)
        u = []
        for _ in range(k - 1 - len(t)):
            x = next(it)
            u.append(x)
        print(*t, *u)
        deqs.append(deque(u))


if __name__ == '__main__':
    main()


Fixed submission:
n = int(input())

k = int((n * 2) ** 0.5) + 1
if k * (k - 1) != 2 * n:
    print('No')
else:
    print('Yes')
    print(k)
    arr = [list() for _ in range(k)]

    num = 1
    tar1, tar2 = 0, 1
    while True:
        arr[tar1].append(num)
        arr[tar2].append(num)
        if num == n:
            break
        else:
            num += 1
        if len(arr[tar1]) == k - 1:
            tar1 += 1
            tar2 = tar1 + 1
        else:
            tar2 += 1
    for i in range(k):
        print(k - 1, *arr[i])
Buggy python submission (verdict: Runtime Error):
from math import gcd


def lcm(x, y):
    return (x * y) // gcd(x, y)


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

l = lcm(n, m)
g = gcd(n, m)

ng = n // g
mg = m // g
k = 0
flg = True
while True:
    if k * ng >= n or k * mg >= m:
        break
    if s[k * ng] != t[k * mg]:
        flg = False
        break
    k += 1

if flg:
    print(l)
else:
    print(-1)

Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


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

l = lcm(n, m)
g = gcd(n, m)

ng = n // g
mg = m // g
k = 0
flg = True
while True:
    if k * ng >= n or k * mg >= m:
        break
    if s[k * ng] != t[k * mg]:
        flg = False
        break
    k += 1

if flg:
    print(l)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction

MOD = 10 ** 9 + 7

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

csum = [0]
t = 0
for i in range(1, n + 1):
    t += Fraction(1, i)
    csum.append(t)

fact = 1
t = 1
while t <= n:
    fact *= t
    fact %= MOD
    t += 1

# jが何回加算されるか
ans = 0
for j in range(n):
    coef = 0
    coef += csum[abs(j - 0) + 1]  # 左側加算
    coef += csum[abs(j - (n - 1)) + 1]  # 右側加算
    coef -= 1  # 自身を減算
    # print(coef, a[j])
    ans += coef * a[j]
    ans %= MOD

ans *= fact
ans %= MOD

print(ans)

Fixed submission:
MOD = 10 ** 9 + 7

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

csum_invs = [0]
t = 0
for i in range(1, n + 1):
    t += pow(i, MOD - 2, MOD)
    t %= MOD
    csum_invs.append(t)
# print(csum_invs)

fact = []
t = 1
for i in range(1, n + 1):
    t *= i
    t %= MOD
    fact.append(t)
# print(fact)

ans = 0
for i in range(n):
    # print(i)
    t = a[i] * (csum_invs[n - i] + csum_invs[i + 1] - 1)
    t %= MOD
    ans += t

ans *= fact[-1]
ans %= MOD

print(ans)

'''
逆元の求め方: フェルマーの小定理
    a ** (-1) ≡ a ** (p - 2) (mod p)
    b / a ≡ b * a **(p - 2)
    だから、/ a をしたければ、* a ** (p -2) をすればよい
'''
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

if M % N == 0:
    print(M // N)
else:
    for x in range(min(M, 10 ** 9) + 1, 0, -1):
        if M % x == 0:
            if M / x >= N:
                print(x)
                exit()

Fixed submission:
N, M = map(int, input().split())

As = []
k = 1
while k * k <= M:
    if M % k == 0:
        As.append(k)
        As.append(M // k)
    k += 1

As = sorted(As, reverse=True)

for ans in As:
    if M // ans >= N:
        print(ans)
        break
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
s = list(input())

g = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 1-indexed -> 0-indexed
    g[a].add(b)  # edge
    g[b].add(a)

q = [True for _ in range(n)]
left = n
i = 0
cnt_ok = 0
while left > 0:
    fa, fb = False, False
    for j in g[i]:
        if s[j] == 'A':
            fa = True
        elif s[j] == 'B':
            fb = True
        if fa and fb:
            break
    if fa and fb:
        cnt_ok += 1
        if cnt_ok == left:
            break
    else:
        s[j] = 'X'  # 除外された頂点
        q[i] = False
        left -= 1
        cnt_ok = 0
    i += 1
    if i == n:
        i = 0

print('Yes' if left > 0 else 'No')

Fixed submission:
'''
https://beta.atcoder.jp/contests/agc027/submissions/3201641
'''
n, m = map(int, input().split())
s = list(input())

deg = [{'A':0, 'B':0} for _ in range(n)]  # deg[0 - (n - 1)][0 - 1] = 0
g = [list() for _ in range(n)]  # g[0 - (n - 1)] = []

for i in range(m):  # クエリを配列に代入
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  # 1-indexed -> 0-indexed
    deg[x][s[y]] += 1  # 頂点 x に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    deg[y][s[x]] += 1  # 頂点 y に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    g[x].append(y)  # 頂点 x に隣接する頂点のリストに y を追加
    g[y].append(x)  # 頂点 y に隣接する頂点のリストに x を追加

was = [False for _ in range(n)]  # was[j] = True なら 頂点 j は que に追加済み
que = []  # A か B が隣接しないため, 連結リストから除外する頂点

for i in range(n):  # 全頂点をループ
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  # A か B が隣接しないなら
        que.append(i)  # 除外頂点リスト que に追加
        was[i] = True  #  was[j] = True は, 除外頂点リスト que に追加済を意味する

for q in que:  # A か B が隣接していない, 除外頂点リストの各頂点をループ（ que はループ中に追加されうる）
    for j in g[q]:  # 除外頂点に隣接する頂点をループ
        deg[j][s[q]] -= 1  # "除外頂点に隣接する頂点" に隣接する頂点の個数を管理 : 除外頂点の文字のカウントを減らす
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  # "除外頂点に隣接する頂点" に A か B が隣接しないなら
            if not was[j]:  # 頂点 j が que に追加済みの頂点でないなら, que に追加する / 追加済みなら, 隣接する頂点の個数管理は, 終了済み
                was[j] = True
                que.append(j)  # 除外頂点リスト que に追加, ループ回数増える

# 除外頂点を取り除いた後に, 頂点が残っていれば, AABB... を作成できる
# 頂点が残っていなければ, つまり, que に全ての頂点が入っていれば, AABB...を作成できない
print('No' if len(que) == n else 'Yes')
Buggy python submission (verdict: Runtime Error):
l = iin()
stack = []

ans = [[1, 2, 0]]
x = l
while True:
    if x == 1:
        break
    while x % 2 == 0:
        x //= 2
        stack.append('*2')
    if x == 1:
        break
    x -= 1
    stack.append('+1')

last_v_num = 2
x = 1#L, つまりパスの数
while len(stack) > 0:
    op = stack.pop()
#    print(op)
    if op == '+1':
        x += 1#パスの数を増やす
        ans.append([1, last_v_num, x - 1])#頂点1と最後の頂点を直接結ぶ, 辺の重みはパスの数 - 1
    elif op == '*2':
        x *= 2#パスの数を増やす
        for i in range(len(ans)):
            ans[i][2] *= 2#w *= 2して, 既存のパスの重みを2倍にする
        #最後の頂点の後ろに, 新たな頂点を加えて結ぶ, 辺の重みは0と1
        ans.append([last_v_num, last_v_num + 1, 0])
        ans.append([last_v_num, last_v_num + 1, 1])
        last_v_num += 1

N = last_v_num
M = len(ans)
print(N, M)
for u, v, w in ans:
    print(u, v, w)

Fixed submission:
def iin(): return int(input())

l = iin()
stack = []

ans = [[1, 2, 0]]
x = l
while True:
    if x == 1:
        break
    #x > 2を条件に加えた理由: 
    #x = 1 -> 2の操作を*2で済ませると[1, 2, 0], [2, 3, 0], [2, 3, 1] となり、
    #頂点数が21以上になるケースが出るため, x = 1 -> 2は+1で済ませる
    while x % 2 == 0 and x > 2:
        x //= 2
        stack.append('*2')
    if x == 1:
        break
    x -= 1
    stack.append('+1')

last_v_num = 2
x = 1#L, つまりパスの数
while len(stack) > 0:
    op = stack.pop()
#    print(op)
    if op == '+1':
        x += 1#パスの数を増やす
        ans.append([1, last_v_num, x - 1])#頂点1と最後の頂点を直接結ぶ, 辺の重みはパスの数 - 1
    elif op == '*2':
        x *= 2#パスの数を増やす
        for i in range(len(ans)):
            ans[i][2] *= 2#w *= 2して, 既存のパスの重みを2倍にする
        #最後の頂点の後ろに, 新たな頂点を加えて結ぶ, 辺の重みは0と1
        ans.append([last_v_num, last_v_num + 1, 0])
        ans.append([last_v_num, last_v_num + 1, 1])
        last_v_num += 1

N = last_v_num
M = len(ans)
print(N, M)
for u, v, w in ans:
   print(u, v, w)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())

x = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    x[L][R] += 1

c = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        c[i][j] += c[i][j - 1] + x[i][j]

for _ in range(Q):
    P, Q = map(int, input().split())
    ans = 0
    for i in range(P, Q + 1):
        ans += c[i][Q] - c[i][P - 1]
    print(ans)


Fixed submission:
def arr(row, column, value): return [[value for _ in range(column)] for _ in range(row)]

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

sum_range = arr(n + 1, n + 1, 0)
#sum_range[0][0] - sum_range[n][n]まで
#初期値0
#行列値は1からnを取るが、累積和を加算する過程で行列を1引いたものを参照するので、[0][0]がエラーにならないと便利？

for _ in range(m):
    L, R = map(int, input().split())
    sum_range[L][R] += 1#(L, R)間を運行す列車の数を代入
    
for L in range(1, n + 1):
    for R in range(1, n + 1):
        #累積和を取る（53:44あたり）
        #https://www.youtube.com/watch?v=OdJH-io-sVw
        sum_range[L][R] += sum_range[L - 1][R]
        sum_range[L][R] += sum_range[L][R - 1]
        sum_range[L][R] -= sum_range[L - 1][R - 1]

#print(sum_range)
for _ in range(q):
    p, q = map(int, input().split())
    ans = sum_range[q][q] - sum_range[p - 1][q] - sum_range[q][p - 1] + sum_range[p - 1][p - 1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, qn = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(m)]
qs = [list(map(int, input().split())) for _ in range(qn)]

r = dict()
for i in range(1, n + 1):
    r[i] = set()
    
l = dict()
for i in range(1, n + 1):
    l[i] = set()

for x in range(len(t)):
    L, R = t[x]
    for i in range(R, n + 1):
        l[i].add(x)
    for i in range(1, L + 1):
        r[i].add(x)

for p, q in qs:
    print(len(r[p] & l[q]))

Fixed submission:
def arr(row, column, value): return [[value for _ in range(column)] for _ in range(row)]

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

sum_range = arr(n + 1, n + 1, 0)
#sum_range[0][0] - sum_range[n][n]まで
#初期値0
#行列値は1からnを取るが、累積和を加算する過程で行列を1引いたものを参照するので、[0][0]がエラーにならないと便利？

for _ in range(m):
    L, R = map(int, input().split())
    sum_range[L][R] += 1#(L, R)間を運行す列車の数を代入
    
for L in range(1, n + 1):
    for R in range(1, n + 1):
        #累積和を取る（53:44あたり）
        #https://www.youtube.com/watch?v=OdJH-io-sVw
        sum_range[L][R] += sum_range[L - 1][R]
        sum_range[L][R] += sum_range[L][R - 1]
        sum_range[L][R] -= sum_range[L - 1][R - 1]

#print(sum_range)
for _ in range(q):
    p, q = map(int, input().split())
    ans = sum_range[q][q] - sum_range[p - 1][q] - sum_range[q][p - 1] + sum_range[p - 1][p - 1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    sq = [1]
    for _ in range(acc_q[n]):
        sq.append(sq[-1] * 3 % MOD)

    ans = 0
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            is_q = int(char == '?')
            rq = acc_q[n] - acc_q[i]
            rc = acc_c[n] - acc_c[i]
            t = (acc_a[i - 1] * (
                    rc * sq[acc_q[n] - is_q]
                    + rq * sq[acc_q[n] - 1 - is_q]
            ) + acc_q[i - 1] * (
                         rc * sq[acc_q[n] - 1 - is_q]
                         + rq * sq[acc_q[n] - 2 - is_q]
                 )) % MOD
            ans = (ans + t) % MOD
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
s = input()
ls = len(s)
dp = [[0 for _ in range(4)] for _ in range(ls+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls+1):
    for j in range(4):
        #'?'のとき'ABC'の3通りに分岐させ、いずれも取らないので3倍
        dp[i][j] += dp[i-1][j] * (3 if s[i-1] == '?' else 1)
        if j > 0:
            #ほしい文字に変えた場合　または　ほしい文字の場合で取ったとき
            dp[i][j] += dp[i-1][j-1] if s[i-1] == 'ABC'[j-1] or s[i-1] == '?' else 0
        dp[i][j] %= mod
print(dp[ls][3])

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    ans = 0
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            t = 0
            t += acc_a[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - int(char == '?'))
            t += acc_a[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 2 - int(char == '?'))
            t %= MOD
            ans = (ans + t) % MOD
    print(int(ans))


if __name__ == '__main__':
    main()


Fixed submission:
s = input()
ls = len(s)
dp = [[0 for _ in range(4)] for _ in range(ls+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls+1):
    for j in range(4):
        #'?'のとき'ABC'の3通りに分岐させ、いずれも取らないので3倍
        dp[i][j] += dp[i-1][j] * (3 if s[i-1] == '?' else 1)
        if j > 0:
            #ほしい文字に変えた場合　または　ほしい文字の場合で取ったとき
            dp[i][j] += dp[i-1][j-1] if s[i-1] == 'ABC'[j-1] or s[i-1] == '?' else 0
        dp[i][j] %= mod
print(dp[ls][3])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from decimal import Decimal

    N = int(input())
    *A, = map(Decimal, input().split())
    A = [x - i for i, x in enumerate(A, start=1)]
    A.sort()

    median = -1
    if N % 2 == 1:
        median = A[N // 2]
    else:
        median = (A[N // 2 - 1] + A[N // 2]) / 2  # ->ここで0.5が生じても偶数個足し合わせてintに戻る

    ans = sum(map(lambda x: abs(x - median), A))
    print(int(ans))


if __name__ == '__main__':
    main()


Fixed submission:
# from statistics import median

n = int(input())
a = map(int, input().split())
a = tuple(sorted(x - i for i, x in enumerate(a, 1)))

# b = median(a)
b = a[n // 2]  # 要素が偶数個のとき、中央値の計算に使用する2値のいずれでもよい

ans = sum(abs(x - b) for x in a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

def inpl(): return input().split()

n, m = map(int, inpl())
M = []
for i in range(n):
    M.append(list(map(int, inpl())))

cake_sets = combinations(M, m)
ans = -1
for c_set in cake_sets:
    val = 0
    for typ in range(3):#x, y, z
        t_val = 0
        for i in range(m):
            t_val += c_set[i][typ]
        val += abs(t_val)
    ans = max(ans, val)
print(ans)
        

Fixed submission:
from operator import mul
from itertools import product

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

ans = 0
for opList in list(product(list((1, -1)), repeat=3)):
    bufArr = []
    for xyz in arr:
        bufArr.append(sum(map(mul, opList, xyz)))
    ans = max(ans, sum(sorted(bufArr, reverse = True)[:m]))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

n, m = map(int, input().split())
arr = []
ans = 0
for i in range(n):
    ##[[x, y, z], ..., [x, y, z]]
    arr.append(list(map(int, input().split())))

cmb = combinations(arr, m)#[[x, y, z],[x, y, z],[x, y, z]]
for xyz in cmb:
    sumXYZ = [0, 0, 0]
    for i in range(m):
        for j in range(3):
            sumXYZ[j] += xyz[i][j]
    ans = max(ans, sum(list(map(abs, sumXYZ))))    

print(ans)

Fixed submission:
from operator import mul
from itertools import product

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

ans = 0
for opList in list(product(list((1, -1)), repeat=3)):
    bufArr = []
    for xyz in arr:
        bufArr.append(sum(map(mul, opList, xyz)))
    ans = max(ans, sum(sorted(bufArr, reverse = True)[:m]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()#西→東方向でi番目並んだ人が向いている向きSi, E=東, W=西

#i番目をリーダーとするとき
#<i番目はE
#i<番目はW

ans = n - 1
for i in range(n):
    buf = 0
    for j in range(n):
        if j < i:
            if s[j] == 'W':
                buf += 1
        if j > i:
            if s[j] == 'E':
                buf += 1
    ans = min(ans, buf)
    
print(ans)

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

w = [0] * (n + 1)
e = [0] * (n + 1)
bfW = 0
bfE = 0
for i in range(n+1):
    w[i] = bfW
    e[i] = bfE
    if s[i] == 'W':
        bfW += 1
    elif s[i] == 'E':
        bfE += 1

ans = n - 1
for i in range(n):
    myW = w[i]
    myE = e[n] - e[i + 1]
    ans = min(ans, myE + myW)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/arc098/submissions/2581691
from math import inf


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)


Fixed submission:
# https://atcoder.jp/contests/arc098/submissions/2581691
inf = float('inf')


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = [int(input()) for _ in range(n)]

a = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for x in p:
    a[x][x] = 1
    for i in range(1, x):
        if a[i][x - 1] == 1:
            a[i][x] = 1

ans = 0
for i in range(1, n + 1):
    ans = max(ans, sum(a[i]))

print(n - ans)

Fixed submission:
n = int(input())
p = [int(input()) for _ in range(n)]

q = [n for _ in range(n)]
for i in range(n):
    q[p[i] - 1] = i

stay_num_cnt = 0
cnt = 0
t = 0
for x in q:
    if x >= t:# x == tはあり得ない
        cnt += 1
    else:
        cnt = 1
    t = x
    stay_num_cnt = max(stay_num_cnt, cnt)
print(n - stay_num_cnt)#, q)
Buggy python submission (verdict: Runtime Error):
s = input()
k = int(input())

sln = len(s)
subs = set()

for ln in range(1, k + 1):
    for i in range(sln):
        subs += s[i:i+ln]
print(sorted(list(subs))[k-1])

Fixed submission:
def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)

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

sln = len(s)
subs = set()

for ln in range(1, sln + 1):
    for i in range(sln):
        subs.add(s[i:i+ln])
print(sorted(list(subs))[k-1])

Fixed submission:
def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)

Buggy python submission (verdict: Runtime Error):
def f(myC, chrs, s, lst):
    for c in chrs:
        if(myC + c) in s:
            lst += [myC + c]
            f(myC + c, chrs, s, lst)
            
if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = []
    f('', chrs, s, lst)
    ##print(lst)
    print(lst[k - 1])

Fixed submission:
def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)

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

lst = set()
s_len = len(s)
for length in range(1, s_len + 1):
    for i in range(s_len):
        myS = s[i:(i + length)]
        if myS != '':
            lst.add(myS)
lst_sorted = sorted(list(lst))
##print(lst_sorted)
print(lst_sorted[k - 1])

Fixed submission:
def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)