Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#python3
def main():
    s = input()
    q = int(input())
    query = []
    for i in range(q):
        t = input()
        query.append(t)
    for i in range(q):
        if query[i][0] == '1':
            #sを反転する
            s = ''.join(reversed(s))
            continue
        if query[i][0] == '2':
            t, f, c = map(str, query[i].split())  
            #あとで消す
            query[i] = (t, f, c)
            #f == 1のとき先頭にcを、f==2のとき最後尾にcを追加する
            if f == '1':
                s = c + s 
            if f == '2':
                s = s + c
    print(s)
main()


Fixed submission:
#python3
def main():
    s = input()
    addfront = ''
    addback = ''
    q = int(input())
    direction = 0
    for i in range(q):
        t = input()
        if t[0] == '1':
            direction += 1
            continue
        if t[0] == '2':
            if direction % 2 == 0:
                if t[2] == '1':
                    addfront = t[4] + addfront 
                if t[2] == '2':
                    addback = addback + t[4]
            else:
                if t[2] == '1':
                    addback = addback + t[4]
                if t[2] == '2':
                    addfront = t[4] + addfront
    ans = addfront + s + addback
    if direction%2 == 0:
        print(ans)
    else:
        ans = ''.join(reversed(ans))
        print(ans)
main()
Buggy python submission (verdict: Runtime Error):
#python3
def main():
    h = int(input())
    n = h//2 + 1
    s = ''.join(['1']*n) 
    ans = int(s, 2)
    print(ans)
main()


Fixed submission:
#python3

def f(x):
    if x == 1:
        return 1
    else:
        return 2*f(x//2)+1

def main():
    h = int(input())
    print(f(h))

main()
Buggy python submission (verdict: Runtime Error):
#python3
INF = int(1e9)
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

def main():
    h, w = map(int, input().split())
    maze = []
    ans = 0
    for _ in range(h):
        data = input()
        maze.append(data)    
    
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                continue
            start = (i, j)
            from collections import deque         
            g = [[INF for _ in range(w)] for _ in range(h)] 
            q = deque()
            q.append(start)
            g[i][j] = 0
            while len(q) > 0:
                x, y = q.popleft()
                for d in dd:
                    di = x + d[0]
                    dj = y + d[1]
                    if (di < 0) | (dj < 0) | (di >= h) | (dj >= w): 
                        continue
                    if maze[di][dj] == "#":
                        continue
                    if g[di][dj] != INF:
                        continue
                    q.append((di, dj))
                    g[di][dj] = g[x][y]+1 
            

        for i in range(h):
            for j in range(w):
                if g[i][j] == INF:
                    continue
                ans = max(ans, g[i][j])
    print(ans)
main()

Fixed submission:
#python3
from collections import deque
from collections import namedtuple

Vertex = namedtuple('Vertex', ['i', 'j'])  
INF = int(1e10)
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def main():
    h, w = map(int, input().split())
    maze = [input() for i in range(h)]
    ans = 0

    for si in range(h):
        for sj in range(w):
            if maze[si][sj] == '#':
                continue 
            dist = [[INF for i in range(w)] for j in range(h)]
            q = deque()

            def update(i, j, x):
                if dist[i][j] != INF:
                    return None
                dist[i][j] = x
                q.append(Vertex(i, j))


            update(si, sj, 0)
            while len(q) != 0:
                i, j = q.popleft()
                for dir in range(4):
                    ni = i+di[dir]
                    nj = j+dj[dir]
                    if (ni < 0) | (ni >= h) | (nj < 0) | (nj >= w):
                        continue

                    if maze[ni][nj] == '#':
                        continue
                    update(ni, nj, dist[i][j]+1)

            for i in range(h):
                for j in range(w):
                    if dist[i][j] == INF:
                        continue
                    ans = max(ans, dist[i][j])

    print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
#python3
INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()

Fixed submission:
#python3
from bisect import bisect_left
INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    ac = [0]
    for i in range(n):
        ac.append(ac[i]+a[i])

    def chk(x):
        cnt = 0
        for i in range(n):
            pos = bisect_left(a, x - a[i])
            cnt += (n-pos)
        return (cnt < m)

    l = 0
    r = INF
    while r-l > 1: 
        mid = (l + r)//2
        if chk(mid):
            r = mid
        else:
            l = mid

    cnt = 0
    sgm = 0
    for i in range(n):
        pos = bisect_left(a, r - a[i])
        cnt += (n-pos) 
        sgm += a[i] * (n-pos) + (ac[n] - ac[pos]) 

    print(sgm+(m-cnt)*l)
main()
Buggy python submission (verdict: Runtime Error):
#usr/bin/python3
a, b = input().split()
print(6-int(a)-int(b))

Fixed submission:
#usr/bin/python3
a = input()
b = input()
print(6-int(a)-int(b))
Buggy python submission (verdict: Runtime Error):
#python3
import math
a,b=map(int, input().split())
print(a*b//(math.gcd(a,b)))


Fixed submission:
#python3
a, b = map(int, input().split())
def gcd(x, y):
  if x%y == 0:
    return y
  else :
    return gcd(y, x%y) 

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

print(lcm(a, b))

Buggy python submission (verdict: Runtime Error):
#python3
import math
a,b=map(int, input().split())
print(a*b//math.gcd(a,b))


Fixed submission:
#python3
a, b = map(int, input().split())
def gcd(x, y):
  if x%y == 0:
    return y
  else :
    return gcd(y, x%y) 

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

print(lcm(a, b))
Buggy python submission (verdict: Runtime Error):
#python3
cnt = 0
s = 1
def main():
    n = int(input())
    a = [int(i) for i in input().split()]

    def solve(ar):
        global cnt
        global s
        idx = 0
        f = False
        for i in range(len(ar)):
            if s == ar[i]:
                idx = i
                cnt += 1
                f = True
                break
        if (not f) or (idx>n):
            return 
        s += 1
        solve(ar[idx+1:])
        return cnt

    p = solve(a)
    print(n-p) if p else print(-1)
main()


Fixed submission:
#python3
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 1
    for i in range(n):
        if a[i] == k:
            k += 1
    k -= 1
    print(n - k) if k else print(-1)  

main()

Buggy python submission (verdict: Runtime Error):
#python3
cnt = 0
s = 1
def main():
    n = int(input())
    a = [int(i) for i in input().split()]

    def solve(ar):
        global cnt
        global s
        idx = 0
        f = False
        for i in range(len(ar)):
            if s == ar[i]:
                idx = i
                cnt += 1
                f = True
                break
        if (not f) or (idx>n):
            return 
        s += 1
        solve(ar[idx+1:])
        return cnt

    p = solve(a)
    print(n-p) if p else print(-1)
main()

Fixed submission:
#python3
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 1
    for i in range(n):
        if a[i] == k:
            k += 1
    k -= 1
    print(n - k) if k else print(-1)  

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations 
from bisect import bisect_left
def main():
    N = int(readline())
    L = [int(i) for i in readline().split()]
    L.sort()
    sig = 0
    for i in range(N):
        for j in range(i+1, N):
            l = bisect_left(L[j+1:], L[i]+L[j])
            sig += l
    print(sig)
if __name__ == '__main__':
    main()


Fixed submission:
#python3
from bisect import bisect_left
def main():
    n = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ab = L[i]+L[j]
            r = bisect_left(L, ab)
            l = j+1
            ans += r-l
    print(ans)
main()
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(n**0.5)+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import math 
def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(math.sqrt(x))+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    g = gcd(A, B)
    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        i = 2
        while i*i <= x:
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
            i += 1
        if x != 1:
            res.append((x, 1))
        return res

    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import math 
def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(math.sqrt(x))+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    g = gcd(A, B)
    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())-1;print(n*(n+1)//2)

Fixed submission:
#python3

def main():
    s = input()
    t = input()
    cnt = 0
    for i,j in zip(s,t):
        if i == j:
            cnt += 1
    print(cnt)
main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    print(sum([i for i in range(1, int(readline()))]))
if __name__ == '__main__':
    main()


Fixed submission:
#python3
n=int(input())
n-=1
print(n*(n+1)//2)

Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    A = np.arange(1, int(readline()), dtype=np.int64)
    print(A.sum())
if __name__ == '__main__':
    main()


Fixed submission:
#python3
n=int(input())
n-=1
print(n*(n+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
def main():
    N = int(readline())
    A = np.zeros(N+1, dtype=np.int64)
    A[1:] = np.array(readline().split(), np.int64)
    table = np.zeros(N+1, dtype=np.int64) 
    for i in reversed(range(1, N+1)):
        table[i] = (table[::i].sum()+A[i])%2

    print(table.sum())
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Fixed submission:
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = [0 for _ in range(n)]
    for i in reversed(range(1, n+1)):
        s = 0
        j = i + i
        while j <= n: 
            s ^= b[j-1]
            j += i
        b[i-1] = s^a[i-1]
    
    m = sum(b)
    print(m)
    for i in range(n):
        if b[i] == 1:
            if i == n-1:
                print(i+1)
            else:
                print(i+1, end=' ')
        
main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
def main():
    N = int(readline())
    A = np.zeros(N+1, dtype=np.int64)
    A[1:] = np.array(readline().split(), np.int64)
    table = np.zeros(N+1, dtype=np.int64) 
    for i in np.arange(1,N+1, dtype=np.int64)[::-1]:
        table[i] = (table[::i].sum()+A[i])%2

    print(table.sum())
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Fixed submission:
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = [0 for _ in range(n)]
    for i in reversed(range(1, n+1)):
        s = 0
        j = i + i
        while j <= n: 
            s ^= b[j-1]
            j += i
        b[i-1] = s^a[i-1]
    
    m = sum(b)
    print(m)
    for i in range(n):
        if b[i] == 1:
            if i == n-1:
                print(i+1)
            else:
                print(i+1, end=' ')
        
main()
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import accumulate
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    Ae = A[1::2]
    Ao = A[::2]
    x1 = (sum(Ao)-sum(Ae))//2
    table = [0]*(N+1)
    table[0] = x1
    def rec(i):
        if i == N:
            return
        table[i+1] = A[i] - table[i]
        rec(i+1)
    rec(0)
    for i in table[:N]:
        print(i*2, end=' ')
if __name__ == '__main__':
    main()


Fixed submission:
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    c = 0
    for i in range(n):
        if i%2 == 0:
            c += a[i]
        else:
            c -= a[i]
    x = c//2
    xs = []
    xs.append(x)
    for i in range(2, n+1):
        z = a[i-2] - xs[i-2]
        xs.append(z)
    for i in range(n):
        xs[i] = 2*xs[i]
    for i in range(n):
        if i == n-1:
            print(xs[i])
        else:
            print(xs[i], end=' ')
main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    sval = sum(a)
    for k in range(1, n+1):
        a_s = 0
        for l in range(n//2):
            a_s += a[((k+1)+(2*l))%n-1]
        ans = sval - 2 * a_s
        print(ans, end=' ')
main()


Fixed submission:
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    c = 0
    for i in range(n):
        if i%2 == 0:
            c += a[i]
        else:
            c -= a[i]
    x = c//2
    xs = []
    xs.append(x)
    for i in range(2, n+1):
        z = a[i-2] - xs[i-2]
        xs.append(z)
    for i in range(n):
        xs[i] = 2*xs[i]
    for i in range(n):
        if i == n-1:
            print(xs[i])
        else:
            print(xs[i], end=' ')
main()

Buggy python submission (verdict: Time Limit Exceeded):
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    sval = sum(a)
    for k in range(1, n+1):
        a_s = 0
        for l in range(n//2):
            a_s += a[((k+1)+(2*l))%n-1]
        ans = sval - 2 * a_s
        print(ans, end=' ')
main()


Fixed submission:
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    c = 0
    for i in range(n):
        if i%2 == 0:
            c += a[i]
        else:
            c -= a[i]
    x = c//2
    xs = []
    xs.append(x)
    for i in range(2, n+1):
        z = a[i-2] - xs[i-2]
        xs.append(z)
    for i in range(n):
        xs[i] = 2*xs[i]
    for i in range(n):
        if i == n-1:
            print(xs[i])
        else:
            print(xs[i], end=' ')
main()
Buggy python submission (verdict: Runtime Error):
#python3
from numpy import lcm
def main():
    a, b, c, d = map(int, input().split())
    p = b - ((b//c + b//d) - b//lcm(c, d))
    q = (a-1) - (((a-1)//c + (a-1)//d) - (a-1)//lcm(c, d))
    print(p-q)
main() 

Fixed submission:
#python3
from fractions import gcd

def lcm(a, b):
    return (a*b)//gcd(a, b)


def main():
    a, b, c, d = map(int, input().split())
    p = b - ((b//c + b//d) - b//lcm(c, d))
    q = (a-1) - (((a-1)//c + (a-1)//d) - (a-1)//lcm(c, d))
    print(p-q)
main()
Buggy python submission (verdict: Runtime Error):
#python3
from itertools import count
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
ans=0
d=0
for i in range(len(l)+1):
  if d>x: 
    break
  d=d+l[i]
  ans=i
print(i)

Fixed submission:
#python3
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
d=0
c=1
for i in range(n):
  d=d+l[i]
  if d<=x:
    c+=1
print(c)

Buggy python submission (verdict: Runtime Error):
#python3
from itertools import count
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
ans=0
d=0
for i in range(110):
  if d>x: 
    break
  d=d+l[i]
  ans=i
print(i)

Fixed submission:
#python3
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
d=0
c=1
for i in range(n):
  d=d+l[i]
  if d<=x:
    c+=1
print(c)

Buggy python submission (verdict: Runtime Error):
#python3
from itertools import count
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
ans=0
d=0
for i in count(0):
  if d>x: 
    break
  d=d+l[i]
  ans=i
print(i)

Fixed submission:
#python3
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
d=0
c=1
for i in range(n):
  d=d+l[i]
  if d<=x:
    c+=1
print(c)

Buggy python submission (verdict: Runtime Error):
#python3
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
cnt=0
d=0
while d<=x:
  d=d+l[cnt]
  cnt+=1
print(cnt)

Fixed submission:
#python3
n,x=map(int, input().split())
l=[int(i) for i in input().split()]
d=0
c=1
for i in range(n):
  d=d+l[i]
  if d<=x:
    c+=1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush, heapify 
def main():
    N, M = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    heapify(A)
    for _ in range(M):
        b, c = map(int, readline().split())
        for i in range(b):
            v = heappop(A)
            if v>=c:
                heappush(A, v)
                break
            else:
                heappush(A, c)
    print(sum(A))     
if __name__ == '__main__':
    main()


Fixed submission:
#python3
from heapq import heappop, heappush

def main():
    n, m = map(int, input().split())
    hq = [] 
    for i in input().split():
        heappush(hq, (-int(i), 1))
    for _ in range(m):
        b, c = map(int, input().split())
        heappush(hq, (-c, b))
    ans = 0
    for i in range(n):
        v, u = heappop(hq)
        u = u - 1
        if u >= 1:
            heappush(hq, (v, u))
        v = - v 
        ans = ans + v
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
#python3
def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    for _ in range(m):
        b, c = map(int, input().split())
        a.extend([c for _ in range(b)])     
    a.sort(reverse=True)
    ans = sum(a[:n])
    print(ans)
main()


Fixed submission:
#python3
from heapq import heappop, heappush

def main():
    n, m = map(int, input().split())
    hq = [] 
    for i in input().split():
        heappush(hq, (-int(i), 1))
    for _ in range(m):
        b, c = map(int, input().split())
        heappush(hq, (-c, b))
    ans = 0
    for i in range(n):
        v, u = heappop(hq)
        u = u - 1
        if u >= 1:
            heappush(hq, (v, u))
        v = - v 
        ans = ans + v
    print(ans)
main()