Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)


Fixed submission:

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = defaultdict(set)

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)


Fixed submission:

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)

Buggy python submission (verdict: Runtime Error):

from collections import defaultdict

N = int(input())
g = defaultdict(set)

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)


Fixed submission:

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))


Fixed submission:

from collections import Counter
import sys

sys.setrecursionlimit(10**6)


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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for h, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))


Fixed submission:
from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))
Buggy python submission (verdict: Runtime Error):
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join())

Fixed submission:
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join(a))

Buggy python submission (verdict: Runtime Error):
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join

Fixed submission:
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join(a))

Buggy python submission (verdict: Runtime Error):
d = int(input())
a=［'Christmas'］
for i in ranage(25-d):
  a.append('Eve')
print(' '.join(a))

Fixed submission:
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join(a))
Buggy python submission (verdict: Runtime Error):
N = int(intpu())
if N % 2 == 0:
  print(N)
else:
  print(N*2)

Fixed submission:
N = int(input())
if N % 2 == 0:
  print(N)
else:
  print(N*2)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B):
    if A <= 6 and B <= 6:
        return 'Yay!'
    else:
        return ':('


def main():
    A = read_int()
    B = read_int()
    print(slv(A, B))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B):
    if A <= 8 and B <= 8:
        return 'Yay!'
    else:
        return ':('


def main():
    # A = read_int()
    # B = read_int()
    A, B = read_int_n()
    print(slv(A, B))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@lru_cache(maxsize=None)
def r(N):
    # print(N)
    if N == 1:
        return 1
    elif N == 0:
        return 0
    a = 1
    b = 6**int(math.floor(math.log(N, 6)))
    c = 9**int(math.floor(math.log(N, 9)))
    if c > 0:
        ac = r(N - c) + 1
    else:
        ac = sys.maxsize
    if b > 0:
        ab = r(N - b) + 1
    else:
        ab = sys.maxsize
    aa = r(N - a) + 1
    return min(aa, ab, ac)


@mt
def slv(N):
    return r(N)


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(50000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@lru_cache(maxsize=None)
def r(N):
    if N == 0:
        return 0

    c = 1
    while True:
        if c * 9 <= N:
            c *= 9
        else:
            break
    b = 1
    while True:
        if b * 6 <= N:
            b *= 6
        else:
            break
    if c >= 9:
        ac = r(N - c) + 1
    else:
        ac = sys.maxsize

    if b >= 6:
        ab = r(N - b) + 1
    else:
        ab = sys.maxsize

    return min(N, ab, ac)


@mt
def slv(N):
    return r(N)


def main():

    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    ans = sys.maxsize
    for i in range(N):
        ans = min(ans, S[:i].count('W') + S[i + 1:].count('E'))
    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):

    W = 0
    E = S.count('E')
    ans = E + W
    for s in S:
        if s == 'E':
            E -= 1

        ans = min(E + W, ans)

        if s == 'W':
            W += 1

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def slv(A):

    count = 0

    for i in range(len(A)):
        for j in range(i + 1, len(A) + 1):
            # print(A[i:j], i, j)
            if sum(A[i:j]) == 0:
                count += 1
                # print(A[i:j], i, j)
    return count


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # print(A)
    print(slv(A))


if __name__ == '__main__':
    main()

Fixed submission:
from collections import Counter


def slv(A):
    S = 0
    C = Counter()
    C[0] += 1
    for a in A:
        S += a
        C[S] += 1

    c = 0
    for v in C.values():
        if v > 1:
            c += (v * (v - 1)) // 2

    return c


def main():
    N = int(input())
    A = list(map(int, input().split()))

    # import random
    # N = 2 * 100000
    # A = [random.randint(-1000000000, 1000000000) for _ in range(N)]

    print(slv(A))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import random


def slv(N, C, X, V):
    # cal_l = 0
    # move = 0
    # for x, v in zip(X, V):
    #     if x-move > v:
    #         break
    #     cal_l += v
    #     move = x
    # cal_l -= move

    # cal_r = 0
    # move = 0
    # tmp =list(zip(X, V))
    # for x, v in tmp[::-1]:
    #     if (C-x)-move > v:
    #         break
    #     cal_r += v
    #     move = C - x
    # cal_r -= move

    # print(cal_l, cal_r)

    ans_l = [(0, 0)]
    for x, v in zip(X, V):
        ans_l.append((x, ans_l[-1][1] + v))

    ans_r = [(0, 0)]
    for x, v in list(zip(X, V))[::-1]:
        ans_r.append((C-x, ans_r[-1][1] + v))


    ans_l_r = []
    for i, a in enumerate(ans_l):
        tmp = 0
        for b in ans_r[:-i]:
            c = a[1] + b[1] - 2*a[0] - b[0]
            tmp = max(tmp, c)
        ans_l_r.append( tmp)
    ans_r_l = []
    for i, a in enumerate(ans_r):
        tmp = 0
        for b in ans_l[:-i]:
            c = a[1] + b[1] - 2*a[0] - b[0]
            tmp = max(tmp, c)
        ans_r_l.append( tmp)

    
    # print(ans_l)
    # print(ans_r)
    l = max([x[1]-x[0] for x in ans_l])
    r = max([x[1]-x[0] for x in ans_r])
    lr = max(ans_l_r)
    rl = max(ans_r_l)


    return max(l, r, lr, rl)



def main():
    N, C = list(map(int, input().split()))
    X = []
    V = []
    for _ in range(N):
        x, v = list(map(int, input().split()))
        X.append(x)
        V.append(v)
    print(slv(N, C, X, V))


if __name__ == '__main__':
    main()

Fixed submission:
import random


def slv(N, C, X, V):
    ans_l = [(0, 0)]
    ans_l_ = [0]
    for x, v in zip(X, V):
        ans_l_.append(max(ans_l_[-1], ans_l[-1][1] + v - x))
        ans_l.append((x, ans_l[-1][1] + v))
    ans_l_.pop(0)
    ans_l.pop(0)

    ans_r = [(0, 0)]
    ans_r_ = [0]
    for x, v in list(zip(X, V))[::-1]:
        ans_r_.append(max(ans_r_[-1], ans_r[-1][1] + v - (C-x)))
        ans_r.append((C-x, ans_r[-1][1] + v))
    ans_r_.pop(0)
    ans_r.pop(0)
        

    # print('p1')

    ans_l_r = []
    for i, a in enumerate(ans_l[:-1], 1):
        # print(ans_r_[N-i-1],  a[1]-2*a[0])
        ans_l_r.append(ans_r_[N-i-1] + a[1]-2*a[0])

    # print('p2')
    ans_r_l = []
    for i, a in enumerate(ans_r[:-1], 1):
        # print(ans_l_[N-i-1],  a[1]-2*a[0])
        ans_r_l.append(ans_l_[N-i-1] + a[1]-2*a[0])

    l = max([x[1]-x[0] for x in ans_l])
    r = max([x[1]-x[0] for x in ans_r])
    lr = 0 if not ans_l_r else max(ans_l_r)
    rl = 0 if not ans_r_l else max(ans_r_l)

    # print(ans_l)
    # print(ans_l_)
    # print(ans_r)
    # print(ans_r_)

    # print(l, r, lr, rl)
    return max(l, r, lr, rl)



def main():
    N, C = list(map(int, input().split()))
    X = []
    V = []
    for _ in range(N):
        x, v = list(map(int, input().split()))
        X.append(x)
        V.append(v)

    # N = 100000
    # C = 1000000000000
    # X = [1]
    # V = [100]
    # for _ in range(N):
    #     X.append(X[-1]+random.randint(1, 10000))
    #     V.append(random.randint(1, 10000))

    print(slv(N, C, X, V))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def mid_1(X):
    return X[(len(X)) // 2]


def mid(X):
    return X[(len(X)) // 2 - 1]


def main():
    N = int(input())

    X = list(map(int, input().split()))
    X_ = X[:]
    X_.sort()
    for i in range(N):
        if X[i] in X_[:N // 2]:
            print(mid_1(X_))
        else:
            print(mid(X_))


if __name__ == '__main__':
    main()

Fixed submission:
import random


def mid_1(X):
    return X[(len(X)) // 2]


def mid(X):
    return X[(len(X)) // 2 - 1]


def main():
    N = int(input())

    X = list(map(int, input().split()))
    # N = 200000
    # X = [random.randint(0, 1000000000) for _ in range(N)]
    X_ = X[:]
    X_.sort()
    X__ = X_[:N // 2]
    X__ = X__[-1]

    x_1 = mid_1(X_)
    x = mid(X_)

    ans = []
    # print(X_)
    # print(X__)
    for i in range(N):
        if X[i] <= X__:
            print(x_1)
            # ans.append(x_1)
        else:
            print(x)
            # ans.append(x)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
if A == B:
  print(0)
else:
  M = sum(A)
  c = 0
  for a, b in zip(A, B):
    c = max(a - b)
  print(M - c)

Fixed submission:
N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
if A == B:
  print(0)
else:
  M = sum(A)
  c = 10**10
  for a, b in zip(A, B):
    if a > b:
      c = min(c, b)
  print(M - c)

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


def main():
    N = int(input())
    A = []
    B = []

    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    c = 0
    while A != B:
        minc = 999999999999
        minc_idx = None
        for i in range(N):
            if A[i] < minc and A[i] != 0:
                minc = A[i]
                minc_idx = i
        A[minc_idx] -= 1
        diff = 999999999999
        diff_idx = None
        for i in range(N):
            if A[i] < diff and B[i] != 0:
                diff = A[i]
                diff_idx = i
        B[diff_idx] -= 1
        c += 1
        # print(A, minc_idx)
        # print(B, diff_idx)

    print(c)


if __name__ == '__main__':
    main()

Fixed submission:
N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
if A == B:
  print(0)
else:
  M = sum(A)
  c = 10**10
  for a, b in zip(A, B):
    if a > b:
      c = min(c, b)
  print(M - c)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python

ALPHA = sorted([a for a in "zyxwvutsrqponmlkjihgfedcba"])


def main():
    S = input()

    if 'zyxwvutsrqponmlkjihgfedcba' == S:
        return -1

    S = [s for s in S]
    ans = []
    for s in S:
        if s in ALPHA:
            ALPHA.remove(s)
            ans.append(s)
        else:
            ans.append(ALPHA.pop(0))
            break
    else:
        ans.append(ALPHA.pop(0))

    print("".join(ans))


if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python
import itertools

ALPHA = sorted([s for s in 'zyxwvutsrqponmlkjihgfedcba'])


def main():
    S = input().strip()

    if 'zyxwvutsrqponmlkjihgfedcba' == S:
        return '-1'

    if len(set(ALPHA) - set([s for s in S])) != 0:
        return S + sorted(set(ALPHA) - set([s for s in S]))[0]

    for i in range(len(S) - 1, 0, -1):
        if S[i - 1] > S[i]:
            pass
        else:
            break

    for a in sorted(set(ALPHA) - set(S[:i])):
        if a > S[i - 1]:
            return S[:i - 1] + a


if __name__ == '__main__':
    ans = main()
    print(ans)